Check if Point Is Reachable

Check if Point Is Reachable

What is this problem about?

This "Hard" coding problem asks if you can reach a target coordinate $(targetX, targetY)$ starting from $(1, 1)$ using a specific set of moves. You can move from $(x, y)$ to $(x, y+x)$, $(x+y, y)$, $(x, 2y)$, or $(2x, y)$. This problem is deceptively simple in its rules but requires deep mathematical insight to solve efficiently.

Why is this asked in interviews?

PhonePe and other fintech companies use this to test a candidate's strength in Number Theory and Math. It’s not a pathfinding problem (BFS would be too slow); it's a Greatest Common Divisor (GCD) problem in disguise. It evaluates whether you can reduce a complex set of rules to a fundamental mathematical property.

Algorithmic pattern used

The core pattern is Number Theory and GCD. The key observation is that the operations $(x, y+x)$ and $(x+y, y)$ are exactly what you do in the Euclidean algorithm for finding the GCD. These operations do not change the $GCD(x, y)$. The other operations, $(2x, y)$ and $(x, 2y)$, allow you to multiply the coordinates (and thus the GCD) by powers of 2. Therefore, a point is reachable if and only if the $GCD(targetX, targetY)$ is a power of 2.

Example explanation

Target: $(4, 7)$

1. Calculate $GCD(4, 7)$. Since 7 is prime and doesn't divide 4, $GCD = 1$.
2. Is 1 a power of 2? Yes ($2^0$).
3. Result: True. Target: $(3, 6)$
4. Calculate $GCD(3, 6) = 3$.
5. Is 3 a power of 2? No.
6. Result: False.

Common mistakes candidates make

The biggest mistake is trying to use Breadth-First Search (BFS) or recursion with memoization. The coordinates can be huge, leading to TLE (Time Limit Exceeded) or memory errors. Another mistake is failing to realize that the "doubling" moves can be thought of as "halving" if you work backwards from the target.

Interview preparation tip

Brush up on the Euclidean algorithm and properties of the Greatest Common Divisor. Many "Hard" grid problems that involve weird movement rules are actually hidden number theory problems. If you see $x+y$ or $x-y$, think GCD!