LeetCode 780 - Reaching Points

The problem asks whether it is possible to transform a starting point (sx, sy) to a target point (tx, ty) using a defined set of operations. Specifically, from a point (x, y), you can either move to (x, x + y) or (x + y, y).

leetcodehardmath

LeetCode Problem 780

Difficulty: 🔴 Hard
Topics: Math

Solution

Problem Understanding

The problem asks whether it is possible to transform a starting point (sx, sy) to a target point (tx, ty) using a defined set of operations. Specifically, from a point (x, y), you can either move to (x, x + y) or (x + y, y). The inputs sx, sy, tx, and ty are all integers in the range [1, 10^9], which means the solution must handle very large numbers efficiently. The expected output is a boolean: true if it is possible to reach (tx, ty) from (sx, sy), or false otherwise.

The constraints indicate that brute-force exploration of all possible moves will be infeasible due to the exponential growth of possible points. Important edge cases include situations where the starting point is already equal to the target point, or when one coordinate exceeds the target early, making the target unreachable. The problem guarantees positive integers, so zero or negative values are not a concern.

The key challenge is reasoning about the growth of (x, y) efficiently without enumerating all sequences of operations.

Approaches

A brute-force approach would explore all possible sequences of moves from (sx, sy) to see if (tx, ty) is reachable. This could be implemented via recursion or BFS, checking both possible moves at each step. While correct in theory, this approach is computationally infeasible because the number of points grows exponentially, and the constraints allow tx and ty to reach up to 10^9.

The optimal approach leverages a key observation: the operations are reversible. Specifically, if you consider the inverse operations from (tx, ty), you can reduce either coordinate by subtracting the other until you potentially reach (sx, sy). This can be further optimized using modulo operations. If tx > ty, the only possible previous step is (tx - k*ty, ty) for some integer k, and similarly if ty > tx, the previous step is (tx, ty - k*tx). We continue this reduction until the coordinates are less than the starting coordinates, at which point we can determine if the target is reachable.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(tx+ty)) O(tx+ty) Explores all possible sequences, infeasible for large inputs
Optimal O(log(max(tx, ty))) O(1) Reduces target coordinates using modulo, very efficient

Algorithm Walkthrough

  1. Start with the target coordinates (tx, ty) and compare them with (sx, sy).
  2. While tx >= sx and ty >= sy, perform the following:
  • If tx == sx and ty == sy, return true because we have reached the start point.
  • If tx > ty, reduce tx using tx %= ty. This simulates undoing the addition operations in reverse.
  • If ty > tx, reduce ty using ty %= tx.
  1. After the loop, check if one coordinate matches the start and the other is reachable via repeated additions:
  • If tx == sx, check if (ty - sy) % sx == 0.
  • If ty == sy, check if (tx - sx) % sy == 0.
  1. If none of these conditions are satisfied, return false.

Why it works: The algorithm works because each move in the forward direction is additive. By using the modulo operation in reverse, we simulate undoing multiple forward moves at once. The invariant is that if (sx, sy) can reach (tx, ty), then by reversing operations through modulo, we will eventually reduce (tx, ty) to (sx, sy).

Python Solution

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

This Python implementation first checks if we have reached the starting point. If not, it reduces the larger of tx or ty using modulo to simulate reversing the forward moves. Special handling is included when one coordinate matches the start but the other may need multiple subtractions to reach the exact start.

Go Solution

func reachingPoints(sx int, sy int, tx int, ty int) bool {
    for tx >= sx && ty >= sy {
        if tx == sx && ty == sy {
            return true
        }
        if tx > ty {
            if ty > sy {
                tx %= ty
            } else {
                return (tx - sx) % ty == 0
            }
        } else {
            if tx > sx {
                ty %= tx
            } else {
                return (ty - sy) % tx == 0
            }
        }
    }
    return false
}

The Go implementation mirrors the Python logic. Integer division and modulo operations behave similarly, so the logic is directly translatable. Edge cases are handled identically.

Worked Examples

Example 1: sx = 1, sy = 1, tx = 3, ty = 5

Step through the loop:

tx ty action
3 5 ty > tx, tx == sx? no, reduce ty %= tx → ty = 5 % 3 = 2
3 2 tx > ty, ty > sy? yes, tx %= ty → tx = 3 % 2 = 1
1 2 ty > tx, tx == sx? yes, check (ty - sy) % sx = (2-1)%1=0 → return True

Example 2: sx = 1, sy = 1, tx = 2, ty = 2

tx ty action
2 2 tx == ty, neither matches sx or sy for modulo → reduce ty %= tx → ty = 0
2 0 tx >= sx && ty >= sy? No → return False

Example 3: sx = 1, sy = 1, tx = 1, ty = 1

Already tx == sx and ty == sy → return True.

Complexity Analysis

Measure Complexity Explanation
Time O(log(max(tx, ty))) Each modulo operation reduces the larger coordinate, similar to Euclidean GCD steps
Space O(1) No additional data structures are used

The complexity is efficient because each modulo operation drastically reduces one of the coordinates, analogous to the Euclidean algorithm.

Test Cases

# test cases
assert Solution().reachingPoints(1, 1, 3, 5) == True  # example 1
assert Solution().reachingPoints(1, 1, 2, 2) == False # example 2
assert Solution().reachingPoints(1, 1, 1, 1) == True  # example 3
assert Solution().reachingPoints(1, 1, 1000000000, 1) == True  # large tx, sy=1
assert Solution().reachingPoints(1, 1, 1, 1000000000) == True  # large ty, sx=1
assert Solution().reachingPoints(2, 3, 10, 17) == False # cannot reach
assert Solution().reachingPoints(3, 7, 3, 7) == True  # same start and target
Test Why
(1,1,3,5) validates normal path with multiple steps
(1,1,2,2) validates unreachable point
(1,1,1,1) validates trivial case
(1,1,10^9,1) tests large target with one coordinate equal to start
(1,1,1,10^9) tests large target with one coordinate equal to start
(2,3,10,17) validates impossible combination
(3,7,3,7) start equals target

Edge Cases

One edge case is when the starting point equals the target. The algorithm handles this immediately with a direct equality check, returning true.

Another edge case is when one coordinate is fixed, and the other is significantly larger, potentially requiring multiple repeated operations. This is handled using the modulo operations to simulate repeated subtractions efficiently, avoiding the need to iterate step by step.

A third edge case is when the target is unreachable because it cannot be expressed as a combination of additions starting from the start. The algorithm correctly identifies this by reducing coordinates with modulo, and if the loop exits without meeting the start point or divisibility conditions, it returns false. This prevents false positives for large numbers.