Reaching Points

The fastest approach is to reverse-engineer from the target (tx, ty) back to the start (sx, sy), reducing the larger coordinate with modulo operations. This leverages the fact that forward moves are additive, so backtracking ensures correctness while avoiding unnecessary branches. Using this math-driven strategy guarantees O(log max(tx,ty)) operations instead of exhaustive simulation, handling large constraints efficiently.

Problem Statement

You are given a starting point (sx, sy) and a target point (tx, ty). You may repeatedly perform operations that convert a point (x, y) into either (x, x + y) or (x + y, y). Determine whether it is possible to reach the target point from the start point using these operations.

Return true if there exists a sequence of operations that transforms (sx, sy) to (tx, ty); otherwise, return false. Constraints: 1 <= sx, sy, tx, ty <= 10^9. Examples: (1,1) -> (3,5) yields true, (1,1) -> (2,2) yields false.

Examples

Example 1

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

Output: true

One series of moves that transforms the starting point to the target is: (1, 1) -> (1, 2) (1, 2) -> (3, 2) (3, 2) -> (3, 5)

Example 2

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

Output: false

Example details omitted.

Example 3

Input: sx = 1, sy = 1, tx = 1, ty = 1

Output: true

Example details omitted.

Constraints

• 1 <= sx, sy, tx, ty <= 109

Solution Approach

Backtracking with modulo

Instead of simulating all forward moves, reduce (tx, ty) toward (sx, sy) by repeatedly subtracting the smaller coordinate from the larger, effectively applying modulo. This efficiently reverses the additive process and avoids combinatorial explosion.

Base cases

Stop recursion or iteration when either coordinate becomes smaller than the corresponding start coordinate. If (tx, ty) equals (sx, sy), return true; if one coordinate falls below the start while the other does not align mathematically, return false.

Handling edge alignment

When one coordinate matches the start, check if the difference of the other coordinate is divisible by the matched start coordinate. This ensures that the remaining steps can be achieved with repeated additive operations along one axis.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log(max(tx,ty))) due to iterative reductions using modulo. Space complexity is O(1) for iterative approach or O(log(max(tx,ty))) for recursion stack.

What Interviewers Usually Probe

• Candidate must identify the additive nature and consider reverse operations.
• Look for recognition of modulo trick to avoid brute-force path enumeration.
• Check if candidate correctly handles large numbers without simulating every move.

Common Pitfalls or Variants

Common pitfalls

• Attempting exhaustive forward recursion causes TLE for large tx or ty.
• Failing to check base cases when one coordinate equals the start leads to incorrect false returns.
• Misapplying modulo when the smaller coordinate is zero or already aligned with start coordinate.

Follow-up variants

• Changing allowed operations to multiply instead of add requires a completely different strategy.
• Restricting moves to one axis per turn tests understanding of additive paths.
• Target coordinates with negative integers add edge cases for modulo reduction logic.

FAQ

What is the main strategy for solving Reaching Points?

The main strategy is to work backward from the target using modulo reductions, reversing additive operations efficiently.

Why is forward simulation inefficient for this problem?

Because forward simulation explores all possible additive paths, which grows exponentially and leads to time limit exceeded errors for large targets.

How do you handle cases where one coordinate matches the start?

Check if the remaining difference in the other coordinate is divisible by the matched start coordinate, ensuring valid additive steps.

What is the time complexity of the optimal approach?

Time complexity is O(log(max(tx,ty))) because each step reduces the larger coordinate significantly via modulo operations.

Can negative numbers appear in Reaching Points solutions?

No, the problem constraints guarantee 1 <= sx, sy, tx, ty <= 10^9, so negative coordinates do not need to be considered.