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 <= 109When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The search works backward from the target toward the start. An even coordinate can be halved, and the larger coordinate can be reduced by the smaller one. A point is reachable when the start appears, and each point is explored only once.
Here's how the algorithm would work step-by-step:
class Solution:
def isReachable(self, target_x: int, target_y: int) -> bool:
points_to_visit = set([(target_x, target_y)])
visited_points = set()
while points_to_visit:
current_x, current_y = points_to_visit.pop()
if current_x == 1 and current_y == 1:
return True
if (current_x, current_y) in visited_points:
continue
visited_points.add((current_x, current_y))
# We explore backwards, so if we're at an even number, we could have come from half of it.
if current_x % 2 == 0:
previous_point = (current_x // 2, current_y)
if previous_point not in visited_points:
points_to_visit.add(previous_point)
if current_y % 2 == 0:
previous_point = (current_x, current_y // 2)
if previous_point not in visited_points:
points_to_visit.add(previous_point)
# The reverse move for (x+y) is (x, y-x) or (x-y, y).
if current_y > current_x:
previous_point = (current_x, current_y - current_x)
if previous_point not in visited_points:
points_to_visit.add(previous_point)
if current_x > current_y:
previous_point = (current_x - current_y, current_y)
if previous_point not in visited_points:
points_to_visit.add(previous_point)
# If the loop finishes without finding (1, 1), it's unreachable.
return FalseA target is reachable exactly when the greatest common divisor of its two coordinates is a power of two, including two to the power zero, which is one. The divisor is computed by repeated remainder, the same way Euclid's algorithm works. A positive number is a power of two when it shares no bits with the number one smaller than itself.
Here's how the algorithm would work step-by-step:
class Solution:
def isReachable(self, target_x: int, target_y: int) -> bool:
def greatest_common_divisor(number_one, number_two):
while number_two:
number_one, number_two = number_two, number_one % number_two
return number_one
# The GCD of reachable coordinates is preserved through reverse operations (subtraction).
# All reachable points must trace back to a state where GCD is related to the initial (1,1) state.
common_divisor = greatest_common_divisor(target_x, target_y)
# Any number that is a power of 2 can be repeatedly divided by 2 until it becomes 1.
# This means we can transform (2^k, 2^k) down to (1, 1), making the target reachable.
is_power_of_two = (common_divisor > 0) and (common_divisor & (common_divisor - 1) == 0)
return is_power_of_two| Case | How to Handle |
|---|---|
| The target is already the starting point | The search recognizes it immediately, and the divisor of the two coordinates is one, which is a power of two. |
| The target is four and seven | Both versions accept it because a sequence of the allowed moves reaches that point. |
| The target is six and nine | Both versions reject it because the greatest common divisor is three, which is not a power of two. |
| One coordinate is one and the other is a power of two | The point is reachable, since the divisor is one. |
| Both coordinates are odd and greater than one | The point is reachable only when their greatest common divisor is one. |