Check if Point Is Reachable
HardPrompt
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 <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
A straightforward but inefficient approach is to treat the problem as a graph traversal problem. The grid points are the nodes of the graph, and the allowed moves are the directed edges. We can start a Breadth-First Search (BFS) from the initial point (1, 1) and explore all reachable points.
Algorithm
- Create a queue and add the starting point
(1, 1). - Create a
visitedset to store points that have already been explored, and add(1, 1)to it. - While the queue is not empty, dequeue a point
(x, y). - If
(x, y)is the target(targetX, targetY), returntrue. - Generate all possible next points from
(x, y):(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)
- For each new point
(nx, ny):- Check if the point is valid (e.g., coordinates are positive).
- To prevent the search from running indefinitely, apply some bounds, for example,
nx <= 2 * targetXandny <= 2 * targetY. This is a heuristic and may not be correct for all cases. - If the point has not been visited, add it to the queue and the
visitedset.
- If the queue becomes empty and the target has not been found, it means the target is unreachable. Return
false.
Walkthrough
We can use a queue to manage the points to visit and a set to keep track of visited points to avoid cycles and redundant computations. The search begins with (1, 1). In each step, we take a point from the queue, check if it's the target, and if not, we generate all possible next points using the four allowed moves. These new, unvisited points are then added to the queue.
However, the coordinates can grow very large, potentially leading to an infinite search space. To make this feasible, we would need to prune the search space by setting some upper bounds on the coordinates. For instance, we might guess that we don't need to explore points with coordinates much larger than the target's. This heuristic is hard to prove correct and, even with it, the number of states to visit is enormous given that targetX and targetY can be up to 10<sup>9</sup>.
import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set; class Solution { // This approach is too slow and will result in Time Limit Exceeded. public boolean isReachable(int targetX, int targetY) { if (targetX == 1 && targetY == 1) { return true; } Queue<long[]> queue = new LinkedList<>(); queue.add(new long[]{1, 1}); Set<String> visited = new HashSet<>(); visited.add("1,1"); // Heuristic bound to prevent infinite search, not guaranteed to be correct. long boundX = 2L * targetX; long boundY = 2L * targetY; while (!queue.isEmpty()) { long[] current = queue.poll(); long x = current[0]; long y = current[1]; long[][] nextMoves = { {x, y - x}, {x - y, y}, {2 * x, y}, {x, 2 * y} }; for (long[] move : nextMoves) { long nx = move[0]; long ny = move[1]; if (nx == targetX && ny == targetY) { return true; } if (nx > 0 && ny > 0 && nx <= boundX && ny <= boundY) { String key = nx + "," + ny; if (!visited.contains(key)) { visited.add(key); queue.add(new long[]{nx, ny}); } } } } return false; }}Complexity
Time
O(V + E), where V (vertices) and E (edges) are related to the size of the search space. This is exponential in the magnitude of the target coordinates and will not pass.
Space
O(targetX * targetY) or larger, depending on the bounds. This is infeasible for the given constraints.
Trade-offs
Pros
Conceptually simple and easy to understand for graph traversal problems.
Cons
Extremely high time complexity, leading to Time Limit Exceeded (TLE) for the given constraints.
Very high space complexity due to the need to store a large number of visited states.
It's difficult to establish correct bounds for the search space. Coordinates might need to become larger than the target before they can be reduced to the target values.
Solutions
Solution
class Solution {public boolean isReachable(int targetX, int targetY) { int x = gcd(targetX, targetY); return (x & (x - 1)) == 0; }private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.