A digital river is a sequence of numbers where every number is followed by the same number plus the sum of its digits. In such a sequence 123 is followed by 129 (since 1 + 2 + 3 = 6), which again is followed by 141.
We call a digital river river K, if it starts with the value K.
For example, river 7 is the sequence beginning with {7, 14, 19, 29, 40, 44, 52, ... } and river 471 is the sequence beginning with {471, 483, 498, 519, ... }.
Digital rivers can meet. This happens when two digital rivers share the same values. River 32 meets river 47 at 47, while river 471 meets river 480 at 519.
Given a number decide, whether it can be a meeting point of two or more digital rivers. For example, it is easy to check that only river 20 contains the number 20 in its sequence (as a starting point).
We call a digital river river K, if it starts with the value K.
For example, river 7 is the sequence beginning with {7, 14, 19, 29, 40, 44, 52, ... } and river 471 is the sequence beginning with {471, 483, 498, 519, ... }.
Digital rivers can meet. This happens when two digital rivers share the same values. River 32 meets river 47 at 47, while river 471 meets river 480 at 519.
Given a number decide, whether it can be a meeting point of two or more digital rivers. For example, it is easy to check that only river 20 contains the number 20 in its sequence (as a starting point).
Input
Line 1: An integer r1.
Output
Line 1 :YES if r1 can be a meeting points of two digital rivers, NO otherwise.
Constraints
1 ≤ r1 < 100000
Solution
The question asks to check if the given number can be a meeting point for two or more rivers. Since you only need to say YES or NO, we don't need to test all possible numbers in a brute-force way. When you look at the series, there are a lot of possible duplicates. By focusing on only the ones that are creating duplicate meeting points it can be shown that starting with \(r_1\) we only need to find one single smaller number that leads to \(r_1\). The maximum number of steps any river can advance is \(9\cdot \lceil r_1\rceil\) and since \(r_1<100000\), we limit the search scope to 45. As such the following implementation solves the problem
r = gets.to_i
puts ([r-45, 1].max..r-1).any?{|n| n + n.digits.sum == r} ? 'YES' : 'NO'