# LeetCode 780: Reaching Points

## Problem Restatement

We are given four integers:

```python
sx, sy, tx, ty
```

The starting point is:

```python
(sx, sy)
```

The target point is:

```python
(tx, ty)
```

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

```text
(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

| Item | Meaning |
|---|---|
| Input | Four integers `sx`, `sy`, `tx`, `ty` |
| Output | `True` if the target can be reached, otherwise `False` |
| Move 1 | Add `y` to `x` |
| Move 2 | Add `x` to `y` |
| Constraint | `1 <= sx, sy, tx, ty <= 10^9` |

Function shape:

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

## Examples

Example 1:

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

One valid sequence is:

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

So the answer is:

```python
True
```

Example 2:

```python
sx = 1
sy = 1
tx = 2
ty = 2
```

This is impossible.

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

```text
(2, 1)
(1, 2)
```

Both coordinates cannot become `2` at the same time.

So the answer is:

```python
False
```

Example 3:

```python
sx = 1
sy = 1
tx = 1
ty = 1
```

The start is already the target.

So the answer is:

```python
True
```

## First Thought: Search Forward

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

```text
(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)`:

```text
(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)`:

| Case | Previous move must have been |
|---|---|
| `tx > ty` | The previous point was `(tx - ty, ty)` |
| `ty > tx` | The previous point was `(tx, ty - tx)` |
| `tx == ty` | Cannot go backward unless already at the start |

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:

```text
(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:

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

So we can replace many subtractions with:

```python
tx %= ty
```

Likewise, if `ty > tx`, use:

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

```python
tx %= ty
```

2. Otherwise, reduce `ty`:

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

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

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

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

```text
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(log max(tx, ty))` | Modulo reductions behave like the Euclidean algorithm |
| Space | `O(1)` | Only integer variables are used |

## Implementation

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

## Code Explanation

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

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

```python
if tx > ty:
    tx %= ty
```

Otherwise, `ty` is larger, so we reduce `ty`:

```python
else:
    ty %= tx
```

After the loop, exact equality is immediately valid:

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

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

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

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

All other cases are impossible:

```python
return False
```

## Testing

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

| Test | Why |
|---|---|
| `(1, 1)` to `(3, 5)` | Standard reachable case |
| `(1, 1)` to `(2, 2)` | Equal target coordinates but unreachable |
| Same start and target | Base case |
| Same `x` coordinate | Checks one-dimensional remainder case |
| Same `y` coordinate | Checks symmetric remainder case |
| Large remaining difference | Checks modulo shortcut |
| Non-multiple difference | Checks final divisibility condition |