Problem statement

https://leetcode.com/problems/reaching-points/

Solution

The idea is start from the end, not from the beginning: in this way we always can make only one step: if we have (a, b) and a < b, then one reverse step is (a, b - a) and if a > b, it is (a - b, b). So, we start from the end and check step by step. To make it faster one reverse step can be done as (a%b, b%a), but in this way we need to make sure that we did not skip any solutions, like we have (100, 7) and we go directly to (2, 7), and we need to check positions (93, 7), (86, 7), ... (9, 7).

Complexity

Time complexity is O(log(sx) + log(sy)).

Code

class Solution:
    def reachingPoints(self, sx, sy, tx, ty):
        while tx > 0 and ty > 0:
            if tx >= ty:
                if sy == ty and (tx-sx)%ty == 0 and tx >= sx: return True
            else:
                if sx == tx and (ty-sy)%tx == 0 and ty >= sy: return True
           
            tx, ty = tx%ty, ty%tx
        
        return False