problemhardalgorithmsleetcode-2543leetcode 2543leetcode2543

Check if Point Is Reachable

HardUpdated: Jul 4, 2025
Practice on:
LeetCode

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

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

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

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

Edge cases:

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

Code

C++
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);
    }
};
Go
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
}
Java
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);
    }
}
Kotlin
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
    }
}
Python
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
Rust
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.

Comments