Sequence Join Point

Problem

We consider a 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 (as 41 = 34 + (3 + 4))
• 41 is itself followed by 46 (46 = 41 + (4 + 1))

Two sequences which 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. After the join point, the sequences are equal.

471 → 483 → 498 → 519 → 534 → ...
                   ↑
480 → 492 → 507 → 519 → 534 → ...
                   |
              Join Point

Your Task: Implement the function compute_join_point(s1, s2) which takes the starting points of two sequences and returns the join point of these sequences.

You are guaranteed that the two given sequences always join, at a joining point lower than 20,000,000.

Constraints

• 1 ≤ s1, s2 ≤ 10^7
• The join point is guaranteed to be < 20,000,000
• Both sequences will eventually meet
• s1 and s2 may be equal (join point would be s1 itself)

Examples

Example 1

Input:

s1 = 471
s2 = 480

Output:

519

Explanation: Sequence from 471: 471 → 483 → 498 → 519 → ... Sequence from 480: 480 → 492 → 507 → 519 → ... They meet at 519.

Example 2

Input:

s1 = 1
s2 = 2

Output:

145

Explanation: Sequence from 1: 1 → 2 → 4 → 8 → 16 → 23 → 28 → 38 → 49 → 62 → 70 → 77 → 91 → 101 → 103 → 109 → 119 → 130 → 134 → 145 Sequence from 2: 2 → 4 → 8 → 16 → 23 → ... (same after 2) Actually: They meet at 2, since seq from 1 contains 2.

Example 3

Input:

s1 = 100
s2 = 100

Output:

100

Explanation: Same starting point, join immediately.

Function Signature

def compute_join_point(s1: int, s2: int) -> int:
    """
    Find where two digit-sum sequences meet.

    Args:
        s1: Starting point of the first sequence
        s2: Starting point of the second sequence

    Returns:
        The first number that appears in both sequences
    """
    pass

Estimated Time

20-25 minutes

Tags

sequences hash-set math simulation medium real-interview