Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/780.html
780. Reaching Points (Hard)
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]
.
Related Topics:
Math
Solution 1.
Starting from (sx, sy)
will get TLE since there are many branches we need to try.
Instead, we should start from (tx, ty)
since there could be only a single valid route.
If tx > ty
, the previous point must be (tx - ty, ty)
.
If tx < ty
, the previous point must be (tx, ty - tx)
.
tx
and ty
can’t be the same otherwise the previous point will have 0
value in the coordinates.
If tx > ty
, instead of keeping subtracting ty
which could be slow when tx
is very large and ty
is very small, we do tx %= ty
. The tx < ty
case is symmetrical.
We loop until tx <= sx
or ty <= sy
, then we have two valid cases:
sx == tx
,ty >= sy
andty - sy
is divisible bysx
.sy == sy
,sx >= tx
andtx - sx
is divisible bysy
.
// OJ: https://leetcode.com/problems/reaching-points/
// Time: O(log(max(tx, ty)))
// Space: O(1)
// Ref: https://leetcode.com/problems/reaching-points/discuss/114856/JavaC%2B%2BPython-Modulo-from-the-End
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (sx < tx && sy < ty) {
if (tx < ty) ty %= tx;
else tx %= ty;
}
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 (tx >= sx && ty >= sy) { if (tx > ty) { if (ty > sy) tx %= ty; else return (tx - sx) % ty == 0; } else if (tx < ty) { if (tx > sx) ty %= tx; else return (ty - sy) % tx == 0; } else break; } return tx == sx && ty == sy; } } ############ class Solution { public boolean reachingPoints(int sx, int sy, int tx, int ty) { while (tx > sx && ty > sy && tx != ty) { if (tx > ty) { tx %= ty; } else { ty %= tx; } } if (tx == sx && ty == sy) { return true; } if (tx == sx) { return ty > sy && (ty - sy) % tx == 0; } if (ty == sy) { return tx > sx && (tx - sx) % ty == 0; } return false; } }
-
// OJ: https://leetcode.com/problems/reaching-points/ // Time: O(log(max(tx, ty))) // Space: O(1) // Ref: https://leetcode.com/problems/reaching-points/discuss/114856/JavaC%2B%2BPython-Modulo-from-the-End class Solution { public: bool reachingPoints(int sx, int sy, int tx, int ty) { while (sx < tx && sy < ty) { if (tx < ty) ty %= tx; else tx %= ty; } return (sx == tx && sy <= ty && (ty - sy) % sx == 0) || (sy == ty && sx <= tx && (tx - sx) % sy == 0); } };
-
class Solution: def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool: while tx > sx and ty > sy and tx != ty: if tx > ty: tx %= ty else: ty %= tx if tx == sx and ty == sy: return True if tx == sx: return ty > sy and (ty - sy) % tx == 0 if ty == sy: return tx > sx and (tx - sx) % ty == 0 return False
-
func reachingPoints(sx int, sy int, tx int, ty int) bool { for tx > sx && ty > sy && tx != ty { if tx > ty { tx %= ty } else { ty %= tx } } if tx == sx && ty == sy { return true } if tx == sx { return ty > sy && (ty-sy)%tx == 0 } if ty == sy { return tx > sx && (tx-sx)%ty == 0 } return false }