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.
This approach involves working backward from the target point `(targetX, targetY)` to the starting point `(1, 1)`. Consider the inverse operations of the allowed steps.
Thus, you can start at `(targetX, targetY)` and repeatedly find the preceding points until you reach `(1, 1)` or determine it's impossible.
The C implementation uses a loop to continuously reduce either targetX or targetY, depending on the greater value. It uses the modulus operator to replicate the reverse of permissible moves, checking if either coordinate can be reduced to 1 while the other is a multiple.
Time Complexity: O(log(max(targetX, targetY)))
Space Complexity: O(1)
Approach 2 uses the Greatest Common Divisor (GCD) property, based on the observation that valid steps only change the relative prime basis of points minimally.
By recursively determining the GCD of targetX and targetY, the task simplifies to checking if one coordinate could shrink to 1 provided it maintains divisibility by the other throughout the recursive checks.
This C function calculates the GCD of the target coordinates and verifies if it's equal to one, a crucial determinant to encapsulate continuity backtracking to `(1,1)`.
Time Complexity: O(log(min(targetX, targetY))) due to the GCD calculation.
Space Complexity: O(1)
We notice that the first two types of moves do not change the greatest common divisor (gcd) of the horizontal and vertical coordinates, while the last two types of moves can multiply the gcd of the horizontal and vertical coordinates by a power of 2. In other words, the final gcd of the horizontal and vertical coordinates must be a power of 2. If the gcd is not a power of 2, then it is impossible to reach.
Next, we prove that any (x, y) that satisfies gcd(x, y)=2^k can be reached.
We reverse the direction of movement, that is, move from the end point back. Then (x, y) can move to (x, x+y), (x+y, y), (\frac{x}{2}, y), and (x, \frac{y}{2}).
As long as x or y is even, we divide it by 2 until both x and y are odd. At this point, if x neq y, without loss of generality, let x \gt y, then \frac{x+y}{2} \lt x. Since x+y is even, we can move from (x, y) to (x+y, y), and then to (\frac{x+y}{2}, y) through operations. That is to say, we can always make x and y continuously decrease. When the loop ends, if x=y=1, it means it can be reached.
The time complexity is O(log(min(targetX, targetY))), and the space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Reverse Operations | Time Complexity: O(log(max(targetX, targetY))) |
| Approach 2: Recursive GCD-based Reduction | Time Complexity: O(log(min(targetX, targetY))) due to the GCD calculation. |
| Mathematics | — |
| 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 |
Check if Point Is Reachable | Biweekly Contest 96 | Leetcode • codingMohan • 1,159 views views
Watch 6 more video solutions →Practice Check if Point Is Reachable with our built-in code editor and test cases.
Practice on FleetCode