In this guide, you will get 780. Reaching Points LeetCode Solution with the best time and space complexity. The solution to Reaching Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given four integers sx, sy, tx, and ty, return true if it is possible to convert the point (sx, sy) to the point (tx, ty) through some operations, or false otherwise.
The allowed operation on some point (x, y) is to convert it to either (x, x + y) or (x + y, y).
Example 1:
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)
Example 2:
Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: false
Example 3:
Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: true
Constraints:
1 <= sx, sy, tx, ty <= 109
Complexity Analysis
Time Complexity: O(\log\max(tx, ty))
Space Complexity: O(1)
780. Reaching Points LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
780. Reaching Points LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
780. Reaching Points LeetCode Solution in Python
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) # code by PROGIEZ
