21. Math

780. Reaching Points

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.

• Every parent point (x, y) has two children, (x, x+y) and (x+y, y). However, every point (x, y) only has one parent candidate (x-y, y) if x >= y, else (x, y-x).

• O(max(tx, ty))

def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
    while tx >= sx and ty >= sy:
        if tx == sx and ty == sy:
            return True
        if tx > ty:
            tx -= ty
        else:
            ty -= tx
    return False

• If either tx or ty is very large, use module to increase speed

• O(log(max(tx, ty)))

def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:       
    while tx >= sx and ty >= sy:
        if tx == ty:
            break
        elif tx > ty:
            if ty > sy:
                tx %= ty
            else:  # ty == sy -> only consider tx side
                return (tx - sx) % ty == 0
        else:
            if tx > sx:
                ty %= tx
            else: 
                return (ty - sy) % tx == 0
    return tx == sx and ty == sy