Watch 10 video solutions for Reaching Points, a hard level problem involving Math. This walkthrough by Tony Teaches has 9,796 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 109Problem Overview: Starting from a point (sx, sy), you can transform it using two operations: (x, y) → (x + y, y) or (x, y) → (x, x + y). The task is to determine whether these operations can produce the target point (tx, ty).
Approach 1: Recursive Backtracking (Exponential Time)
This approach simulates the process exactly as described in the problem. From (sx, sy), recursively apply both operations and explore the resulting states until either the target (tx, ty) is reached or the coordinates exceed the target values. Because each state branches into two possibilities, the search tree grows quickly and leads to exponential time complexity O(2^k), where k is the number of operations performed. Space complexity is O(k) due to the recursion stack. While this approach demonstrates the mechanics of the transformation well, it becomes infeasible for large coordinates since the search space explodes.
Approach 2: Reverse Operation with Modulo Optimization (O(log n))
The key observation is that the forward process only increases values. Instead of building from (sx, sy), work backward from (tx, ty). If the last move produced (tx, ty), then the previous state must have been either (tx - ty, ty) or (tx, ty - tx). Repeated subtraction simulates reversing the operation, but doing this one step at a time would still be slow for large numbers. A faster trick uses the modulo operator: if tx > ty, replace tx with tx % ty; if ty > tx, replace ty with ty % tx. This compresses many subtraction steps into a single operation, similar to the Euclidean algorithm used for GCD. Continue until either the coordinates match the start point or one coordinate drops below the start. Time complexity becomes O(log(max(tx, ty))) and space complexity is O(1). The solution relies heavily on reasoning about number transitions, which connects naturally with Math and Number Theory patterns.
Recommended for interviews: The reverse modulo approach is what interviewers typically expect. It shows you can transform a brute-force forward simulation into a mathematical reduction problem. Discussing the recursive backtracking approach first demonstrates understanding of the rules, while transitioning to the reverse greedy strategy highlights optimization skills and familiarity with patterns related to Recursion and arithmetic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Backtracking | O(2^k) | O(k) | Useful for understanding the forward transformation rules or demonstrating brute-force reasoning in interviews |
| Reverse Operation with Modulo Optimization | O(log(max(tx, ty))) | O(1) | Optimal solution for large coordinates; uses mathematical reduction similar to the Euclidean algorithm |