Codingame Solution: The River II.

Original Problem

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).

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'

« Back to problem overview