Determine Whether One Point Can Reach Another
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Determine Whether One Point Can Reach Another
You start at a point `(sx, sy)` with positive integer coordinates. From `(x, y)`, one move may transform the point into either:
- `(x + y, y)`, or
- `(x, x + y)`.
Given positive integers `sx`, `sy`, `tx`, and `ty`, return whether the target `(tx, ty)` is reachable from the start.
Implement:
```python
def solve(sx: int, sy: int, tx: int, ty: int) -> bool:
...
```
## Constraints
- `1 <= sx, sy, tx, ty <= 10^18`
## Examples
```text
(1, 1) -> (3, 5) = True
(1, 1) -> (2, 2) = False
(3, 7) -> (3, 7) = True
```
Quick Answer: Determine whether a target point with positive integer coordinates can be reached from a starting point using two coordinate-addition moves. Account for values as large as 10^18, targets equal to the start, impossible coordinate relationships, and exact reachability.
Implement solve(sx, sy, tx, ty). Coordinates are positive integers supplied as decimal strings so every language preserves values up to 10^18 exactly. One move changes (x, y) to either (x + y, y) or (x, x + y). Return whether the target is reachable from the start.
Constraints
- sx, sy, tx, and ty are decimal strings for values from 1 through 10^18.
- All moves use exact positive-integer arithmetic.
Examples
Input: ('1', '1', '3', '5')
Expected Output: True
Explanation: Checks equality, repeated moves, unreachable gcd states, and exact large coordinates.
Input: ('1', '1', '2', '2')
Expected Output: False
Explanation: Checks equality, repeated moves, unreachable gcd states, and exact large coordinates.
Hints
- Work backward because the larger target coordinate identifies the last move.
- Replace repeated subtraction with a remainder, while handling a coordinate already equal to its start value.