Problem
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 <= 10^9
Solution
/**
* @param {number} sx
* @param {number} sy
* @param {number} tx
* @param {number} ty
* @return {boolean}
*/
var reachingPoints = function(sx, sy, tx, ty) {
if(sx>tx || sy>ty)
return false;
if(sx===tx && sy===ty)
return true;
if(tx>ty){
var sub=Math.floor((tx-sx)/ty);
if(sub==0)
return false;
return reachingPoints(sx,sy,tx-sub*ty,ty);
}
else
{
var sub=Math.floor((ty-sy)/tx);
if(sub==0)
return false;
return reachingPoints(sx,sy,tx,ty-sub*tx);
}
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).