Watch 7 video solutions for Check if Point Is Reachable, a hard level problem involving Math, Number Theory. This walkthrough by codingMohan has 1,159 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There exists an infinitely large grid. You are currently at point (1, 1), and you need to reach the point (targetX, targetY) using a finite number of steps.
In one step, you can move from point (x, y) to any one of the following points:
(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)Given two integers targetX and targetY representing the X-coordinate and Y-coordinate of your final position, return true if you can reach the point from (1, 1) using some number of steps, and false otherwise.
Example 1:
Input: targetX = 6, targetY = 9 Output: false Explanation: It is impossible to reach (6,9) from (1,1) using any sequence of moves, so false is returned.
Example 2:
Input: targetX = 4, targetY = 7 Output: true Explanation: You can follow the path (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7).
Constraints:
1 <= targetX, targetY <= 109Problem Overview: Starting from point (1,1), you can repeatedly transform the coordinates using operations that add one coordinate to the other or double one coordinate. Given (targetX, targetY), determine whether it is possible to reach that point. The challenge is recognizing how these operations affect the greatest common divisor of the coordinates.
Approach 1: Reverse Operations (O(log(max(x,y))) time, O(1) space)
Instead of constructing the path forward from (1,1), work backward from (targetX, targetY). The reverse of doubling is dividing by two when the coordinate is even, and the reverse of adding coordinates is subtracting the smaller value from the larger. Repeatedly apply these reductions: divide by 2 if possible, otherwise subtract the smaller coordinate from the larger. This gradually shrinks the pair until it either reaches (1,1) or becomes impossible to reduce further.
The key observation is that subtraction preserves the gcd(x, y), while dividing by 2 only removes factors of two. Because the numbers shrink quickly, the loop runs in logarithmic time. This approach mirrors the Euclidean algorithm and highlights how the allowed moves interact with math properties of the coordinates.
Approach 2: Recursive GCD-based Reduction (O(log n) time, O(1) space)
A stronger insight eliminates simulation entirely. Addition operations do not change the greatest common divisor of the coordinates, while doubling multiplies the gcd by 2. Since the starting point (1,1) has gcd = 1, any reachable point must have a gcd that is a power of two. If the gcd contained any odd factor greater than 1, no sequence of valid operations could produce it.
So the solution reduces to computing g = gcd(targetX, targetY). If g is a power of two, the point is reachable; otherwise it is not. Checking this condition is simple using the bit trick g & (g - 1) == 0. This approach relies on properties from number theory and the classic Euclidean algorithm.
This mathematical reduction is extremely efficient and avoids iterative coordinate manipulation entirely.
Recommended for interviews: The GCD-based approach. Interviewers expect you to recognize that the operations preserve gcd except for powers of two introduced by doubling. Showing the reverse-operations reasoning first demonstrates understanding of the transformation process, while deriving the gcd power-of-two condition shows deeper algorithmic insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Operations | O(log(max(x,y))) | O(1) | When reasoning about the problem through simulation and understanding how operations reduce coordinates |
| GCD Power-of-Two Check | O(log n) | O(1) | Best approach for production or interviews; relies on number theory insight |