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.
Example
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
Notice
sx, sy, tx, ty will all be integers in the range [1, 10^9].
分析
不断%=更小的数字直到sx或sy，最后判断 (tx-sy)%sx
class Solution:
"""
@param sx: x for starting point
@param sy: y for starting point
@param tx: x for target point
@param ty: y for target point
@return: if a sequence of moves exists to transform the point (sx, sy) to (tx, ty)
"""
def reachingPoints(self, sx, sy, tx, ty):
# write your code here
while sx < tx and sy < ty:
if tx < ty:
ty %= tx
else:
tx %= ty
# return sx == tx and (ty-sx)%sy == 0 or sy == ty and (tx-sy)%sx == 0
return sx == tx and (ty-sy)%sx == 0 or sy == ty and (tx-sx)%sy == 0