Algorithm
Problem Name: 780. Reaching Points
Problem Link: https://leetcode.com/problems/reaching-points/
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool reachingPoints(int sx, int sy, int tx, int ty){
#if 0
if (sx == tx && sy == ty) return true;
if (sx > tx || sy > ty) return false;
return (reachingPoints(sx, sx + sy, tx, ty) ||
reachingPoints(sx + sy, sy, tx, ty));
#else
while (tx >= sx && ty >= sy) {
if (tx == sx && ty == sy) return true;
if (tx > ty) {
tx -= ty;
} else {
ty -= tx;
}
}
return false;
#endif
}
Input
sx = 1, sy = 1, tx = 3, ty = 5
Output
true
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const reachingPoints = function(sx, sy, tx, ty) {
while (tx >= sx && ty >= sy) {
if (tx === ty) break;
if (tx > ty) {
if (ty > sy) tx %= ty;
else return (tx - sx) % ty === 0;
} else {
if (tx > sx) ty %= tx;
else return (ty - sy) % tx === 0;
}
}
return tx === sx && ty === sy;
};
Input
sx = 1, sy = 1, tx = 3, ty = 5
Output
true
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def reachingPoints(self, sx, sy, tx, ty):
while sxInput
sx = 1, sy = 1, tx = 2, ty = 2
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0780_ReachingPoints
{
public bool ReachingPoints(int sx, int sy, int tx, int ty)
{
while (tx >= sx && ty >= sy)
{
if (tx == ty) break;
if (tx > ty)
{
if (ty > sy) tx %= ty;
else
return (tx - sx) % ty == 0;
}
else
{
if (tx > sx) ty %= tx;
else
return (ty - sy) % tx == 0;
}
}
return (tx == sx && ty == sy);
}
}
}
Input
sx = 1, sy = 1, tx = 2, ty = 2
Output
false