# Reaching Points
**Difficulty:** HARD
[External](https://leetcode.com/problems/reaching-points)
Canonical: https://scaleengineer.com/dsa/problems/reaching-points
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [KLA](https://scaleengineer.com/companies/kla), [Wayfair](https://scaleengineer.com/companies/wayfair), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Coursera](https://scaleengineer.com/companies/coursera), [Workday](https://scaleengineer.com/companies/workday)
---
## Problem
Given four integers `sx`, `sy`, `tx`, and `ty`, return `true` _if it is possible to convert the point_ `(sx, sy)` _to the point_ `(tx, ty)` _through some operations_ _, or_ `false` _otherwise_.

The allowed operation on some point `(x, y)` is to convert it to either `(x, x + y)` or `(x + y, y)`.

**Example 1:**

**Input:** sx = 1, sy = 1, tx = 3, ty = 5
**Output:** true
**Explanation:**
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 3:**

**Input:** sx = 1, sy = 1, tx = 1, ty = 1
**Output:** true

**Constraints:**

* `1 <= sx, sy, tx, ty <= 109`

# Approaches
## Brute-Force Recursive Search
This approach uses a straightforward depth-first search (DFS) starting from the source point `(sx, sy)`. We recursively explore the two possible moves from any point `(x, y)`: `(x, x + y)` and `(x + y, y)`. The search continues until we either reach the target point `(tx, ty)` or the current coordinates exceed the target coordinates, at which point that search path is abandoned.
**Time:** O(2^(tx+ty)). The search space can be visualized as a binary tree. The depth of this tree can be on the order of `tx + ty`, leading to an exponential number of states to explore. This is computationally infeasible for the given constraints. · **Space:** O(tx + ty). The space complexity is determined by the maximum depth of the recursion stack. In the worst case, the depth can be proportional to the sum of the target coordinates.
**Pros:** Simple to understand and implement.; Correctly represents the problem's state transitions.
**Cons:** Extremely inefficient and will not pass for the given constraints.; Leads to a `Time Limit Exceeded` error on most platforms.; Can cause a `StackOverflowError` for paths that are very long, as the recursion depth can become very large.
### Explanation
The core idea is to model the problem as a state-space search. The starting state is `(sx, sy)`. From any state `(x, y)`, we can transition to two new states. We can implement this search using recursion.

A recursive function, say `canReach(current_x, current_y)`, is defined to check if the target is reachable from the current point.

- **Base Cases:**
  - If `current_x == tx` and `current_y == ty`, we have successfully reached the target. The function should return `true`.
  - If `current_x > tx` or `current_y > ty`, we have overshot the target. Since the coordinates only increase with each operation, this path is invalid. The function should return `false` to prune this branch of the search.

- **Recursive Step:**
  - The function makes two recursive calls to explore both possible moves:
    1. `canReach(current_x, current_x + current_y)`
    2. `canReach(current_x + current_y, current_y)`
  - If either of these calls returns `true`, it means a valid path to the target exists, so the function propagates `true` up the call stack.
  - If both calls return `false`, no path exists from the current point, and the function returns `false`.

The initial call to start the search would be `canReach(sx, sy)`.

```java
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) {
            return false;
        }
        if (sx == tx && sy == ty) {
            return true;
        }
        // Explore both possible moves
        return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
    }
}
```
### Algorithm
1. Define a recursive function `solve(x, y, tx, ty)`.
2. **Base Case 1:** If `x == tx` and `y == ty`, a path has been found, so return `true`.
3. **Base Case 2:** If `x > tx` or `y > ty`, the current path has overshot the target. Since coordinates only increase, this path is invalid. Return `false`.
4. **Recursive Step:** Explore the two possible next states:
   - Call `solve(x + y, y, tx, ty)`.
   - Call `solve(x, x + y, tx, ty)`.
5. Return `true` if either of the recursive calls returns `true`, otherwise return `false`.

## Iterative Backward Approach
Instead of searching forward from `(sx, sy)`, which has a branching factor of two, we can work backward from `(tx, ty)`. The key observation is that the reverse operation is deterministic. If a point `(x, y)` was generated from a parent `(px, py)`, then either `(x, y) = (px, px + py)` or `(x, y) = (px + py, py)`. This means the parent of `(x, y)` is uniquely determined: it must be `(x-y, y)` if `x > y`, or `(x, y-x)` if `y > x`. This transforms the search problem into tracing a single, deterministic path backward.
**Time:** O(max(tx, ty)). The number of iterations is proportional to the number of subtractions needed. In the worst-case scenario, such as reaching `(10^9, 1)` from `(1, 1)`, we would subtract 1 repeatedly, leading to linear time complexity. · **Space:** O(1). We only use a few variables to store the current coordinates, regardless of the input size.
**Pros:** Significantly more efficient than the brute-force forward search.; Uses constant space, making it very memory-efficient.
**Cons:** This approach can still be too slow and result in a `Time Limit Exceeded` error if one coordinate is much larger than the other. For example, if `tx = 10^9` and `ty = 1`, the loop would perform nearly `10^9` subtractions.
### Explanation
We can iteratively apply the reverse transformation starting from `(tx, ty)` and see if we can reach `(sx, sy)`.

We use a loop that continues as long as the current point, let's call it `(current_tx, current_ty)`, is potentially reachable from `(sx, sy)` (i.e., `current_tx >= sx` and `current_ty >= sy`).

Inside the loop:
- If `(current_tx, current_ty)` is identical to `(sx, sy)`, we have successfully traced the path back, and we return `true`.
- If `current_tx > current_ty`, the previous point in the sequence must have been `(current_tx - current_ty, current_ty)`. We update `current_tx` accordingly.
- If `current_ty > current_tx`, the previous point must have been `(current_tx, current_ty - current_tx)`. We update `current_ty` accordingly.
- If `current_tx == current_ty` but we haven't reached `(sx, sy)`, we are stuck. A point `(c, c)` with `c > 0` can only be generated from `(c, 0)` or `(0, c)`, which are not possible given the problem constraints (`sx, sy >= 1`). Therefore, we can stop.

If the loop terminates because `current_tx < sx` or `current_ty < sy`, it means we have gone past the start point without hitting it, so it's impossible to reach. In this case, we return `false`.

```java
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == sx && ty == sy) {
                return true;
            }
            if (tx > ty) {
                tx -= ty;
            } else if (ty > tx) {
                ty -= tx;
            } else {
                // tx == ty but not equal to (sx, sy), so we are stuck.
                break;
            }
        }
        return false;
    }
}
```
### Algorithm
1. Initialize `current_tx = tx` and `current_ty = ty`.
2. Use a `while` loop that continues as long as `current_tx >= sx` and `current_ty >= sy`.
3. Inside the loop, first check if `current_tx == sx` and `current_ty == sy`. If so, return `true`.
4. If `current_tx > current_ty`, the only possible parent is `(current_tx - current_ty, current_ty)`. Update `current_tx -= current_ty`.
5. Else if `current_ty > current_tx`, the parent is `(current_tx, current_ty - current_tx)`. Update `current_ty -= current_ty`.
6. Else (`current_tx == current_ty` but not equal to the start point), no valid reverse move exists. Break the loop.
7. If the loop finishes without returning `true`, it means the start point was not reached. Return `false`.

## Optimized Backward Approach with Modulo
This approach is a significant optimization of the backward iterative method. The process of repeatedly subtracting a smaller number from a larger one (e.g., `tx = tx - ty` multiple times) is mathematically equivalent to the modulo operation (`tx = tx % ty`). By using the modulo operator, we can perform many subtraction steps at once, which dramatically reduces the number of iterations required. This technique is analogous to how the standard Euclidean algorithm for finding the greatest common divisor is optimized from using subtraction to using division/modulo.
**Time:** O(log(max(tx, ty))). The number of steps in the `while` loop is determined by the logic of the Euclidean algorithm, which is known to be logarithmic with respect to the values of the inputs. · **Space:** O(1). No extra space that scales with the input size is used.
**Pros:** Extremely efficient, with logarithmic time complexity.; Handles very large numbers within the given constraints without timing out.; Uses constant space.
**Cons:** The logic involving the modulo operator and the final checks is slightly more complex to reason about compared to the direct subtraction method.
### Explanation
We work backward from `(tx, ty)` but accelerate the process using modulo arithmetic.

The main loop continues as long as `tx` is strictly greater than `sx` and `ty` is strictly greater than `sy`. Inside the loop:
- If `tx > ty`, we know that all previous steps must have been of the form `(x, y) -> (x+y, y)`. This means we were subtracting `ty` from `tx` repeatedly. We can do all these subtractions in one go by setting `tx = tx % ty`.
- If `ty > tx`, we do the same for `ty`: `ty = ty % tx`.
- If `tx == ty`, the loop terminates, and since `tx > sx` and `ty > sy`, it's impossible to reach `(sx, sy)`.

Once the loop finishes, we know that either `tx <= sx` or `ty <= sy`. At this point, we can no longer apply the modulo logic because we might overshoot `sx` or `sy`. We must perform a final check:

1.  **Case 1: `tx == sx`**. For this to be a valid path, we must be able to reach `(sx, sy)` from the current `(sx, ty)` by only using the `(x, y) -> (x, y-x)` reverse move. This means `ty` must have been formed by adding `sx` to `sy` some number of times. This is possible if and only if `ty >= sy` and `(ty - sy)` is a multiple of `sx`.
2.  **Case 2: `ty == sy`**. Similarly, we must be able to reach `(sx, sy)` from `(tx, sy)`. This is possible if and only if `tx >= sx` and `(tx - sx)` is a multiple of `sy`.

If neither of these cases holds, it's impossible to reach the target.

```java
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        if (tx < sx || ty < sy) {
            return false;
        }

        while (tx > sx && ty > sy) {
            if (tx > ty) {
                tx %= ty;
            } else {
                ty %= tx;
            }
        }

        // After the loop, one of tx or ty is <= its start value.
        // The other coordinate must match its start value, and the difference
        // in the remaining coordinate must be a multiple of the matched coordinate.
        if (tx == sx && ty >= sy) {
            return (ty - sy) % sx == 0;
        }
        if (ty == sy && tx >= sx) {
            return (tx - sx) % sy == 0;
        }

        return false;
    }
}
```
### Algorithm
1. Handle the trivial case: if `tx < sx` or `ty < sy`, return `false`.
2. Use a `while` loop that continues as long as `tx > sx` and `ty > sy`.
3. Inside the loop, if `tx > ty`, update `tx` to `tx % ty`. Otherwise, update `ty` to `ty % tx`. If at any point `tx` or `ty` becomes 0 due to the modulo operation (e.g., `10 % 5 = 0`), the loop condition will handle it correctly on the next iteration.
4. After the loop terminates, one of the coordinates (`tx` or `ty`) has been reduced to be less than or equal to its starting counterpart (`sx` or `sy`).
5. Check the final conditions:
   - If `tx == sx` and `ty >= sy`, the remaining distance `(ty - sy)` must be coverable by repeatedly adding `sx`. This is true if `(ty - sy) % sx == 0`.
   - If `ty == sy` and `tx >= sx`, the remaining distance `(tx - sx)` must be coverable by repeatedly adding `sy`. This is true if `(tx - sx) % sy == 0`.
6. If none of these conditions are met, return `false`.

# Solutions
### Java

```java
class Solution {
public
  boolean reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx > sx && ty > sy && tx != ty) {
      if (tx > ty) {
        tx %= ty;
      } else {
        ty %= tx;
      }
    }
    if (tx == sx && ty == sy) {
      return true;
    }
    if (tx == sx) {
      return ty > sy && (ty - sy) % tx == 0;
    }
    if (ty == sy) {
      return tx > sx && (tx - sx) % ty == 0;
    }
    return false;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  bool reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx > sx && ty > sy && tx != ty) {
      if (tx > ty)
        tx %= ty;
      else
        ty %= tx;
    }
    if (tx == sx && ty == sy)
      return true;
    if (tx == sx)
      return ty > sy && (ty - sy) % tx == 0;
    if (ty == sy)
      return tx > sx && (tx - sx) % ty == 0;
    return false;
  }
};

```