What is the main strategy to solve Check if Point Is Reachable?

The main strategy is to work backwards from the target coordinates using allowed reverse operations until reaching (1,1) or an invalid state.

Why do we check parity and even/odd conditions in this problem?

Parity and even/odd checks help determine which reverse moves are valid and prevent impossible sequences that cannot reach (1,1).

Can a forward-only approach from (1,1) work efficiently?

No, forward-only simulation leads to exponential growth of possibilities, making the solution inefficient for large coordinates.

How does number theory guide move selection in this problem?

Number theory allows reduction rules like dividing even coordinates and subtracting smaller from larger, ensuring only valid sequences toward (1,1) are considered.

What are common mistakes when implementing this solution?

Common mistakes include ignoring reverse moves, not handling even/odd cases, and missing stopping conditions, which can lead to incorrect results or infinite loops.

#2543

Hard

auto_awesome数学·结合·number·theory

LeetCode 题解工作台

判断一个点是否可以到达

给你一个无穷大的网格图。一开始你在 (1, 1) ，你需要通过有限步移动到达点 (targetX, targetY) 。每一步，你可以从点 (x, y) 移动到以下点之一： (x, y - x) (x - y, y) (2 * x, y) (x, 2 * y) 给你两个整数 targetX 和 …

数学数论

题目描述

给你一个无穷大的网格图。一开始你在 (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 <= 10⁹

lightbulb

解题思路

方法一：数学

我们注意到，前两种移动方式不会改变横、纵坐标的最大公约数，而后两种移动方式可以使得横、纵坐标的最大公约数乘上 $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)$ 。

1

2

3

4

5

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

speed

复杂度分析

指标	值
时间	and space complexity depend on how many reverse operations are applied. In the worst case, each step roughly halves a coordinate or subtracts values, giving logarithmic bounds, but exact performance varies with the input pattern.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate attempting a reverse approach from target to origin.
question_mark
Watch for correct handling of even and odd coordinate cases using number theory.
question_mark
Assess whether the solution avoids unnecessary recursion and infinite loops.

warning

常见陷阱

外企场景

error
Trying only forward moves from (1,1) leads to excessive search space.
error
Ignoring parity and GCD constraints can cause incorrect true results.
error
Failing to stop recursion or loops when coordinates cannot reduce causes infinite computation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine reachability on a grid where moves allow multiplication or division by 3 instead of 2.
arrow_right_alt
Find the minimum number of steps required to reach a target point using the same move rules.
arrow_right_alt
Check reachability with additional diagonal moves combining x and y increments.

help

常见问题

外企场景

继续练习

#2523 范围内最接近的两个质数 #2521 数组乘积中的不同质因数数目 #2513 最小化两个数组中的最大值