Question

2543. Check if Point Is Reachable

中文文档

Description

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 <= 109

Solutions

Solution 1: Mathematics

We notice that the first two types of moves do not change the greatest common divisor (gcd) of the horizontal and vertical coordinates, while the last two types of moves can multiply the gcd of the horizontal and vertical coordinates by a power of $2$. In other words, the final gcd of the horizontal and vertical coordinates must be a power of $2$. If the gcd is not a power of $2$, then it is impossible to reach.

Next, we prove that any $(x, y)$ that satisfies $gcd(x, y)=2^k$ can be reached.

We reverse the direction of movement, that is, move from the end point back. Then $(x, y)$ can move to $(x, x+y)$, $(x+y, y)$, $(\frac{x}{2}, y)$, and $(x, \frac{y}{2})$.

As long as $x$ or $y$ is even, we divide it by $2$ until both $x$ and $y$ are odd. At this point, if $x \neq y$, without loss of generality, let $x \gt y$, then $\frac{x+y}{2} \lt x$. Since $x+y$ is even, we can move from $(x, y)$ to $(x+y, y)$, and then to $(\frac{x+y}{2}, y)$ through operations. That is to say, we can always make $x$ and $y$ continuously decrease. When the loop ends, if $x=y=1$, it means it can be reached.

The time complexity is $O(\log(\min(targetX, targetY)))$, and the space complexity is $O(1)$.

class Solution:
  def isReachable(self, targetX: int, targetY: int) -> bool:
    x = gcd(targetX, targetY)
    return x & (x - 1) == 0

class Solution {
  public boolean isReachable(int targetX, int targetY) {
    int x = gcd(targetX, targetY);
    return (x & (x - 1)) == 0;
  }

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

class Solution {
public:
  bool isReachable(int targetX, int targetY) {
    int x = gcd(targetX, targetY);
    return (x & (x - 1)) == 0;
  }
};

func isReachable(targetX int, targetY int) bool {
  x := gcd(targetX, targetY)
  return x&(x-1) == 0
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  }
  return gcd(b, a%b)
}

function isReachable(targetX: number, targetY: number): boolean {
  const x = gcd(targetX, targetY);
  return (x & (x - 1)) === 0;
}

function gcd(a: number, b: number): number {
  return b == 0 ? a : gcd(b, a % b);
}