Check if point is reachable

Math Number Theory

44.8% acceptance

Feb 25, 2026

262

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

fn gcd_2543(a: i32, b: i32) -> i32 {
  if b == 0 { a } else { gcd_2543(b, a % b) }
}

impl Solution {
  pub fn is_reachable(target_x: i32, target_y: i32) -> bool {
    // Can reach (targetX, targetY) from (1,1) iff gcd(targetX, targetY) is a power of 2
    let g = gcd_2543(target_x, target_y);
    g & (g - 1) == 0
  }
}