Reaching Points

Reaching Points

What is this problem about?

The Reaching Points problem asks whether you can reach point (tx, ty) from (sx, sy) using operations: either (x, y) → (x+y, y) or (x, y) → (x, x+y). This hard math problem works backwards — from (tx, ty) → (sx, sy) — to avoid the exponential forward expansion. The math interview pattern is demonstrated.

Why is this asked in interviews?

J.P. Morgan, Goldman Sachs, Microsoft, Amazon, and Google ask this because working backwards with modulo arithmetic turns an exponential problem into an O(log max) problem. It tests the insight that the backwards path is deterministic (only one predecessor exists).

Algorithmic pattern used

Reverse with modulo. Work backwards: if tx > ty, the previous step was (tx-ty, ty). But instead of subtracting one by one, subtract as many times as possible: tx %= ty (while tx > ty and tx > sx). Similarly for ty > tx. Stop when tx==sx or ty==sy and verify the other coordinate.

Example explanation

sx=1, sy=1, tx=3, ty=5.

• tx=3 < ty=5: ty %= tx → 5%3=2. ty=2.
• tx=3 > ty=2: tx %= ty → 3%2=1. tx=1.
• tx==sx=1. Check: ty (current=2) can reach sy=1? (ty-sy)%sx==(2-1)%1==0 ✓. Return true.

sx=1, sy=1, tx=2, ty=2: tx==ty, can only get here from (1,2) or (2,1), not (1,1). Return false.

Common mistakes candidates make

• Working forward (exponential expansion).
• Not using modulo (subtracting one at a time is O(max) instead of O(log max)).
• Incorrect handling when one coordinate equals the source.
• Not checking the final validation condition carefully.

Interview preparation tip

Reaching Points demonstrates the "reverse and modulo" technique for tree/path problems. Working backwards with modulo converts O(max) to O(log max). The key insight: in reverse, there's only one possible predecessor (either x-y or y-x, whichever is larger was the result of addition). Practice similar reverse-engineering problems: "reverse Euclidean steps," "GCD via subtraction vs modulo."