Check if Point Is Reachable

Problem

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, andfalse otherwise.

Examples

Example 1

1
2
3


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

1
2
3


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

Solution

Method 1 – GCD and Parity Analysis

Intuition

The allowed moves either double a coordinate or subtract one coordinate from the other. This suggests that the greatest common divisor (GCD) and the parity (odd/even) of the coordinates are preserved or change in a predictable way. The key is to analyze the GCD and its properties under these operations.

Reasoning

Doubling a coordinate does not change the GCD, and subtracting one coordinate from the other also preserves the GCD. Thus, the GCD of (targetX, targetY) must be a power of two for the point to be reachable from (1, 1), since the GCD of (1, 1) is 1 and only powers of two can be reached by repeated doublings. If the GCD is not a power of two, the point is not reachable.

Approach

Compute the GCD of targetX and targetY.
Check if the GCD is a power of two (i.e., gcd & (gcd - 1) == 0).
Return true if it is, otherwise false.

Edge cases:

If either coordinate is 1, the other must be a power of two.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
public:
    bool isReachable(int targetX, int targetY) {
        int g = gcd(targetX, targetY);
        return (g & (g - 1)) == 0;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func isReachable(targetX, targetY int) bool {
    var gcd func(int, int) int
    gcd = func(a, b int) int {
        if b == 0 {
            return a
        }
        return gcd(b, a%b)
    }
    g := gcd(targetX, targetY)
    return g&(g-1) == 0
}

1
2
3
4
5
6
7
8
9


class Solution {
    public boolean isReachable(int targetX, int targetY) {
        int g = gcd(targetX, targetY);
        return (g & (g - 1)) == 0;
    }
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

1
2
3
4
5
6
7


class Solution {
    fun isReachable(targetX: Int, targetY: Int): Boolean {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % a)
        val g = gcd(targetX, targetY)
        return g and (g - 1) == 0
    }
}

1
2
3
4
5
6
7
8


class Solution:
    def is_reachable(self, targetX: int, targetY: int) -> bool:
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return a
        g = gcd(targetX, targetY)
        return g & (g - 1) == 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


impl Solution {
    pub fn is_reachable(target_x: i32, target_y: i32) -> bool {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 {
                let t = b;
                b = a % b;
                a = t;
            }
            a
        }
        let g = gcd(target_x, target_y);
        g & (g - 1) == 0
    }
}

Complexity

⏰ Time complexity: O(log(max(targetX, targetY))), as GCD computation is logarithmic in the input size.
🧺 Space complexity: O(1), as only a constant amount of space is used.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – GCD and Parity Analysis#

Intuition#

Reasoning#

Approach#

Code#

Complexity#