Sequence Join Point

Problem

We consider the sequence of numbers where a number is followed by the same number plus the sum of its digits. For example, 34 is followed by 41 (since 41 = 34 + (3 + 4)); 41 is itself followed by 46 (46 = 41 + (4 + 1)).

Two sequences that start from different numbers may join at a given point. For example, the sequence starting from 471 and the sequence starting from 480 share the number 519 (the join point) in their sequence:

471 -> 483 -> 498 -> 519 -> ... 480 -> 492 -> 507 -> 519 -> ...

After the join point, the two sequences are equal forever.

Implement:

compute_join_point(s1: int, s2: int) -> int

which takes the starting points of two sequences and returns the join point.

Constraints

• 1 <= s1, s2
• The two sequences are guaranteed to join at a value below 20_000_000.

Example

Input: s1 = 471, s2 = 480 Output: 519

Hint 1: Both sequences are strictly increasing next(n) = n + sum_of_digits(n) and sum_of_digits(n) >= 1 for any positive n, so each sequence increases monotonically. That means once one sequence overtakes the other, the smaller one can simply be advanced step by step until it catches up — there is no need to look back.

Hint 2: Two-pointer race Maintain two cursors a = s1 and b = s2. While a != b, advance whichever is smaller by one step. Because both sequences are monotonic and guaranteed to meet, this loop terminates at the join point. No hash sets, no reverse lookup — just walk forward.

Full Solution ` def digit_sum(n): total = 0 while n > 0: total += n % 10 n //= 10 return total

def compute_join_point(s1, s2): a, b = s1, s2 while a != b: if a < b: a += digit_sum(a) else: b += digit_sum(b) return a `

Approach:

1. Compute digit_sum(n) by repeatedly taking n % 10 and dividing by 10.
2. Walk both sequences with two cursors. At each step, advance the smaller cursor by digit_sum(cursor).
3. The loop ends when the cursors agree — that value is the join point.

Why it works: both sequences are strictly increasing. If a < b, advancing a is the only way they can ever meet at a shared value (advancing b only widens the gap). The problem guarantees a join below 20_000_000, so the loop terminates.

Time Complexity: O(J / d) where J is the join value and d is the average digit sum (~d ≈ 1). In practice well under a few million iterations even for large s1, s2.

Space Complexity: O(1).

Common pitfalls:

• Using a set of all values in one sequence and then walking the other through the set works but uses unnecessary memory. The two-pointer walk is both faster and constant space.
• Always advancing the smaller pointer is essential — alternating advances or always advancing a will skip past the join point.