LeetCode 780: Reaching Points

Problem Restatement

We are given four integers:

sx, sy, tx, ty

The starting point is:

(sx, sy)

The target point is:

(tx, ty)

From any point (x, y), we may perform one of two moves:

(x, y) -> (x + y, y)
(x, y) -> (x, x + y)

Return True if we can reach (tx, ty) from (sx, sy). Otherwise, return False.

Input and Output

Function shape:

class Solution:
    def reachingPoints(
        self,
        sx: int,
        sy: int,
        tx: int,
        ty: int
    ) -> bool:
        ...

Examples

Example 1:

sx = 1
sy = 1
tx = 3
ty = 5

One valid sequence is:

(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

So the answer is:

True

Example 2:

sx = 1
sy = 1
tx = 2
ty = 2

This is impossible.

From (1, 1), the next points are:

(2, 1)
(1, 2)

Both coordinates cannot become 2 at the same time.

So the answer is:

False

Example 3:

sx = 1
sy = 1
tx = 1
ty = 1

The start is already the target.

So the answer is:

True

First Thought: Search Forward

A direct idea is to start from (sx, sy) and try both moves:

(x, y) -> (x + y, y)
(x, y) -> (x, x + y)

This forms a search tree.

At each point, we branch into two new points.

We can stop when either coordinate becomes larger than the target coordinate.

This works for small numbers, but it is far too slow when coordinates may be as large as 10^9.

Problem With Forward Search

Going forward creates many possible paths.

For example, from (1, 1):

(1, 1)
(2, 1), (1, 2)
(3, 1), (2, 3), (3, 2), (1, 3)
...

The number of possible states grows quickly.

But going backward is much simpler.

If we are at (tx, ty):

The larger coordinate must have been created by adding the smaller coordinate to it.

Key Insight

Work backward from (tx, ty) to (sx, sy).

Forward moves only increase coordinates.

So backward moves only decrease coordinates:

(tx, ty) -> (tx - ty, ty)    when tx > ty
(tx, ty) -> (tx, ty - tx)    when ty > tx

Instead of subtracting one time at a time, we can use modulo.

If tx > ty, then repeated backward steps look like:

(tx, ty)
(tx - ty, ty)
(tx - 2 * ty, ty)
(tx - 3 * ty, ty)
...

So we can replace many subtractions with:

tx %= ty

Likewise, if ty > tx, use:

ty %= tx

This is the same idea as the Euclidean algorithm.

Algorithm

While both target coordinates are still larger than the starting coordinates:

1. If tx > ty, reduce tx:

tx %= ty

2. Otherwise, reduce ty:

ty %= tx

We stop when at least one coordinate is no longer larger than the start coordinate.

Then we check the remaining cases.

If both coordinates match exactly:

tx == sx and ty == sy

return True.

If tx == sx, then only ty still needs to be reduced. This is possible only if the difference is a multiple of tx:

(ty - sy) % tx == 0

If ty == sy, then only tx still needs to be reduced. This is possible only if the difference is a multiple of ty:

(tx - sx) % ty == 0

Otherwise, return False.

Correctness

We prove that the algorithm returns True exactly when (sx, sy) can reach (tx, ty).

Forward moves only add one coordinate to the other. Therefore, both coordinates never decrease. If a target coordinate becomes smaller than the corresponding start coordinate while working backward, then reaching the target is impossible.

Now consider a target point (tx, ty).

If tx > ty, the last forward move could only have been:

(tx - ty, ty) -> (tx, ty)

The other move would have changed ty, not tx. So the backward step must reduce tx by ty.

If ty > tx, the symmetric argument shows that the backward step must reduce ty by tx.

Using modulo is valid because it compresses many repeated backward subtractions of the same smaller coordinate. It does not skip any possible branch, since the backward predecessor is forced by which coordinate is larger.

The loop stops when one coordinate equals or falls below its starting coordinate. At that point, only one coordinate may still vary.

If tx == sx, then the only possible remaining backward operation is repeatedly subtracting tx from ty. Therefore, we can reach sy exactly when ty - sy is a nonnegative multiple of tx.

If ty == sy, the same reasoning applies to tx: we can reach sx exactly when tx - sx is a nonnegative multiple of ty.

If neither coordinate matches the start coordinate after the loop, no valid sequence remains.

Therefore, the algorithm is correct.

Complexity

Implementation

class Solution:
    def reachingPoints(
        self,
        sx: int,
        sy: int,
        tx: int,
        ty: int
    ) -> bool:
        while tx > sx and ty > sy and tx != ty:
            if tx > ty:
                tx %= ty
            else:
                ty %= tx

        if tx == sx and ty == sy:
            return True

        if tx == sx:
            return ty > sy and (ty - sy) % tx == 0

        if ty == sy:
            return tx > sx and (tx - sx) % ty == 0

        return False

Code Explanation

The loop keeps reducing the target while both coordinates are still above the start:

while tx > sx and ty > sy and tx != ty:

If tx is larger, it must have been produced by repeatedly adding ty, so we reduce it by modulo:

if tx > ty:
    tx %= ty

Otherwise, ty is larger, so we reduce ty:

else:
    ty %= tx

After the loop, exact equality is immediately valid:

if tx == sx and ty == sy:
    return True

If the x coordinate matches, the y coordinate must be reachable by adding x repeatedly:

if tx == sx:
    return ty > sy and (ty - sy) % tx == 0

If the y coordinate matches, the x coordinate must be reachable by adding y repeatedly:

if ty == sy:
    return tx > sx and (tx - sx) % ty == 0

All other cases are impossible:

return False

Testing

def run_tests():
    s = Solution()

    assert s.reachingPoints(1, 1, 3, 5) is True
    assert s.reachingPoints(1, 1, 2, 2) is False
    assert s.reachingPoints(1, 1, 1, 1) is True

    assert s.reachingPoints(1, 1, 1, 10) is True
    assert s.reachingPoints(1, 1, 10, 1) is True

    assert s.reachingPoints(3, 7, 3, 28) is True
    assert s.reachingPoints(3, 7, 3, 29) is False

    assert s.reachingPoints(9, 5, 12, 8) is False

    print("all tests passed")

run_tests()

Test coverage: