# 780. Reaching Points

A move consists of taking a point `(x, y)` and transforming it to either `(x, x+y)` or `(x+y, y)`.

Given a starting point `(sx, sy)` and a target point `(tx, ty)`, return `True` if and only if a sequence of moves exists to transform the point `(sx, sy)` to `(tx, ty)`. Otherwise, return `False`.

``````Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True
``````

Note:

• `sx, sy, tx, ty` will all be integers in the range `[1, 10^9]`.

``````class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (tx >= sx && ty >= sy) {
if (tx > ty) {
if (ty == sy) return (tx - sx) % ty == 0;
tx %= ty;
} else {
if (tx == sx) return (ty - sy) % tx == 0;
else ty %= tx;
}
}
return tx == sx && ty == sy;
}
};
``````

``````class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (tx >= sx && ty >= sy) {
if (tx > ty) tx %= ty;
else ty %= tx;
}
if (tx > ty) return tx == sx && ty == sy % sx;
return ty == sy && tx == sx % sy;
}
};
``````

``````class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
if (tx < sx || ty < sy) return false;
while (tx >= sx && ty >= sy) {
if (tx > ty) tx %= ty;
else ty %= tx;
}
if (tx == sx) return (ty - sy) % sx == 0;
if (ty == sy) return (tx - sx) % sy == 0;
return false;
}
};
``````

``````class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
if (tx < sx || ty < sy) return false;
if (tx == sx && (ty - sy) % sx == 0) return true;
if (ty == sy && (tx - sx) % sy == 0) return true;
return reachingPoints(sx, sy, tx % ty, ty % tx);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/780

https://leetcode.com/problems/reaching-points/solution/

https://leetcode.com/problems/reaching-points/discuss/114726/C++-Simple-iterative.

https://leetcode.com/problems/reaching-points/discuss/122916/concise-c++-solution

https://leetcode.com/problems/reaching-points/discuss/116110/C++-iterative-solution

https://leetcode.com/problems/reaching-points/discuss/114732/Java-Simple-solution-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation