Reaching Points
HardMath
Description
Given starting point (sx, sy) and target point (tx, ty), return true if you can reach target using operations: (x, y) -> (x+y, y) or (x, x+y).
Examples
Input:
sx = 1, sy = 1, tx = 3, ty = 5Output:
trueExplanation:
(1,1)->(1,2)->(3,2)->(3,5).
Input:
sx = 1, sy = 1, tx = 2, ty = 2Output:
falseExplanation:
From (1,1), the only possible moves are to (1,2) or (2,1). Neither of those can reach (2,2) since each operation adds one coordinate to the other, always producing an odd sum.
Input:
sx = 1, sy = 1, tx = 1000000000, ty = 1Output:
trueExplanation:
Working backward from (1000000000, 1), repeatedly subtracting the smaller coordinate from the larger reaches (1,1), so the target is reachable.
Constraints
- •
1 ≤ sx, sy, tx, ty ≤ 10⁹
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.