Is Possible Path (Grid Reachability)

Problem On an infinite grid you start at cell (a, b) and want to reach (c, d). From (x, y) you may move to (x+y, y) or (x, x+y). Determine whether (c, d) is reachable.

Input / Output

• Input: four positive integers a, b, c, d.
• Output: boolean — reachable or not.

Constraints

• Values up to 10^9 — forward BFS explodes; the intended solution is O(log max(c,d)).

Example

• (1,1) → (5,3): yes (1,1)→(1,2)→(3,2)→(5,2)? check: (3,2)→(5,2) via x+y=5 ✓ then (5,2)→(5,7)… target (5,3): (1,1)→(2,1)→(3,1)→(3,4)? Use (1,1)→(2,1)→(3,1)→... (5,3) reachable? — work an example both directions in the interview.

Expected approach

• Work backwards from (c, d): the previous state of (x, y) with x > y must be (x−y, y), and vice versa — the larger coordinate was the last one updated. Repeated subtraction is the Euclidean algorithm, so jump with modulo: while both > targets, replace larger l with l % smaller. Terminate when one coordinate matches a and check the other reaches b by exact multiples of the fixed coordinate. O(log max) like gcd.