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 <= 109The key insight in #2543 Check if Point Is Reachable is to analyze the mathematical properties of the allowed operations rather than simulating moves. Direct simulation quickly becomes infeasible because coordinates can grow large. Instead, observe that the operations preserve certain number theoretic relationships between x and y.
By working backward and studying how values change, we notice that the greatest common divisor (GCD) of the coordinates plays a critical role. Addition-based transformations behave similarly to steps in the Euclidean algorithm, while doubling operations only introduce factors of 2. This leads to a crucial observation: the reachability of a point depends on whether the gcd(x, y) can be reduced to 1 by removing powers of two.
Thus, instead of exploring paths, compute gcd(x, y) and check its structure using bit or number theory checks. This reduces the problem to a constant-space mathematical test with logarithmic time complexity due to the GCD computation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| GCD + Power of Two Check | O(log(min(x, y))) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Let’s go in reverse order, from (targetX, targetY) to (1, 1). So, now we can move from (x, y) to (x+y, y), (x, y+x), (x/2, y) if x is even, and (x, y/2) if y is even.
When is it optimal to use the third and fourth operations?
Think how GCD of (x, y) is affected if we apply the first two operations.
How can we check if we can reach (1, 1) using the GCD value calculate above?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The allowed transformations behave similarly to Euclidean algorithm steps, meaning the gcd of the coordinates remains invariant except for factors of two. By analyzing the gcd, we can determine reachability without simulating operations.
Yes, problems involving gcd properties and number theory tricks appear frequently in top tech interviews. This problem tests a candidate's ability to convert a simulation problem into a mathematical observation.
The optimal approach uses number theory. Compute the gcd of the target coordinates and check whether it is a power of two. This works because the allowed operations only introduce factors of two and preserve gcd relationships.
No special data structure is required. The problem is solved using mathematical reasoning and the Euclidean algorithm for computing the gcd, which runs in logarithmic time.