LeetCode Solutions
780. Reaching Points
Time: $O(\log N)$, where $N = \max(tx, ty)$ Space: $O(1)$
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (sx < tx && sy < ty)
if (tx > ty)
tx %= ty;
else
ty %= tx;
return sx == tx && sy <= ty && (ty - sy) % sx == 0 ||
sy == ty && sx <= tx && (tx - sx) % sy == 0;
}
};
class Solution {
public boolean reachingPoints(int sx, int sy, int tx, int ty) {
while (sx < tx && sy < ty)
if (tx > ty)
tx %= ty;
else
ty %= tx;
return sx == tx && sy <= ty && (ty - sy) % tx == 0 ||
sy == ty && sx <= tx && (tx - sx) % ty == 0;
}
}
class Solution:
def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
while sx < tx and sy < ty:
tx, ty = tx % ty, ty % tx
return sx == tx and sy <= ty and (ty - sy) % tx == 0 or \
sy == ty and sx <= tx and (tx - sx) % ty == 0