2543. 判断一个点是否可以到达

English Version

题目描述

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。

每一步 ，你可以从点 (x, y) 移动到以下点之一：

• (x, y - x)
• (x - y, y)
• (2 * x, y)
• (x, 2 * y)

给你两个整数 targetX 和 targetY ，分别表示你最后需要到达点的 X 和 Y 坐标。如果你可以从 (1, 1) 出发到达这个点，请你返回true ，否则返回 false 。

 

示例 1：

输入：targetX = 6, targetY = 9
输出：false
解释：没法从 (1,1) 出发到达 (6,9) ，所以返回 false 。

示例 2：

输入：targetX = 4, targetY = 7
输出：true
解释：你可以按照以下路径到达：(1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7) 。

 

提示：

• 1 <= targetX, targetY <= 109

解法

方法一：数学

我们注意到，前两种移动方式不会改变横、纵坐标的最大公约数，而后两种移动方式可以使得横、纵坐标的最大公约数乘上 $2$ 的幂次。也就是说，最后的横、纵坐标的最大公约数必须是 $2$ 的幂次。最大公约数不是 $2$ 的幂次，那么就无法到达。

接下来，我们证明，任意满足 $gcd(x, y)=2^k$ 的 $(x, y)$ 均可达。

我们将移动方式反转一下，即从终点往回走，那么 $(x, y)$ 可以移动到 $(x, x+y)$, $(x+y, y)$, $(\frac{x}{2}, y)$ 和 $(x, \frac{y}{2})$。

只要 $x$ 或 $y$ 是偶数，我们就将其除以 $2$，直到 $x$ 和 $y$ 均为奇数。此时，若 $x \neq y$，不妨设 $x \gt y$，那么 $\frac{x+y}{2} \lt x$。由于 $x+y$ 是偶数，我们可以通过操作从 $(x, y)$ 移动到 $(x+y, y)$，再移动到 $(\frac{x+y}{2}, y)$。也就是说，我们总能让 $x$ 和 $y$ 不断变小。循环结束时，如果 $x=y=1$，说明可以到达。

时间复杂度 $O(\log(min(targetX, targetY)))$，空间复杂度 $O(1)$。

Python3

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

Java

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);
    }
}

C++

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

Go

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)
}

TypeScript

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);
}

...