Welcome to Subscribe On Youtube
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 Xcoordinate and Ycoordinate 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 <= 10^{9}
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 { 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; } };

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

func isReachable(targetX int, targetY int) bool { x := gcd(targetX, targetY) return x&(x1) == 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); }