Skip to main content

Check if Point is Reachable

Problem​

There exists an infinitely large grid. You are currently at point (1,1)(1, 1), and you need to reach the point (targetX,targetY)(targetX, targetY) using a finite number of steps.

In one Step, you can move from point (x,y)(x, y) to any one of the following points:

  • (x,y−x)(x, y - x)

  • (x−y,y)(x - y, y)

  • (2∗x,y)(2 * x, y)

  • (x,2∗y)(x, 2 * y)

Given two integers targetXtargetX and targetYtargetY representing the X-coordinate and Y-coordinate of your final position, return truetrue if you can reach the point from (1,1)(1, 1) using some number of steps, and falsefalse otherwise.

Examples​

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 <= 10^9

Approach​

To solve the problem, we need to understand the nature of the allowed moves:

  1. (x,y−x)(x, y - x)

  2. (x−y,y)(x - y, y)

  3. (2∗x,y)(2 * x, y)

  4. (x,2∗y)(x, 2 * y)

These moves suggest that if we can reach a certain point '(x, y)', we can generate other points by specific transformations. By analyzing the moves:

  • The first two moves involve subtraction, reducing one coordinate.

  • The last two moves involve multiplication by 22.

We can reverse the logic to check whether we can reach (1,1)(1, 1) from (targetX,targetY)(targetX, targetY). This reversal involves:

  • Checking if targetXtargetX or targetYtargetY can be divided by 22 (to reverse the multiplication).

  • Checking if one coordinate can be reduced by subtracting the other.

By reversing the operations, we trace the problem back to whether (targetX,targetY)(targetX, targetY) can be reduced to (1,1)(1, 1).

The key insight here is that we only need to check if 'gcd(targetX, targetY)' is a power of 22. This is because if both targetXtargetX and targetYtargetY share a common factor other than 22, it won't be possible to reach (1,1)(1, 1).

Solution for Check if Point is Reachable​

The given problem involves reaching a target point (targetX,targetY)(targetX, targetY) from the starting point (1,1)(1, 1) using a set of allowed moves. The challenge is to determine whether it's possible to reach the target using these moves.

Code in Java​

class Solution {
public boolean isReachable(int targetX, int targetY) {
return Integer.bitCount(gcd(targetX, targetY)) == 1;
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}

Complexity Analysis​

Time Complexity: O(log(min(targetX,targetY)))O(log(min(targetX, targetY)))​

Reason: Calculating the gcd of two numbers takes O(log(min(targetX,targetY)))O(log(min(targetX, targetY))) time using the Euclidean algorithm.

Space Complexity: O(1)O(1)​

Reason: The space complexity is O(1)O(1) since we are using a constant amount of extra space for computation (ignoring the space used by the recursive stack of the gcd function, which is logarithmic in terms of the depth of the recursion).

References