780

780. Reaching Points (Hard)

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.

Examples:
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)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True

Note:

• sx, sy, tx, ty will all be integers in the range [1, 10^9].

Related Topics:
Math

Solution 1.

Starting from (sx, sy) will get TLE since there are many branches we need to try.

Instead, we should start from (tx, ty) since there could be only a single valid route.

If tx > ty, the previous point must be (tx - ty, ty).

If tx < ty, the previous point must be (tx, ty - tx).

tx and ty can't be the same otherwise the previous point will have 0 value in the coordinates.

If tx > ty, instead of keeping subtracting ty which could be slow when tx is very large and ty is very small, we do tx %= ty. The tx < ty case is symmetrical.

We loop until tx <= sx or ty <= sy, then we have two valid cases:

• sx == tx, ty >= sy and ty - sy is divisible by sx.
• sy == sy, sx >= tx and tx - sx is divisible by sy.

// OJ: https://leetcode.com/problems/reaching-points/
// Author: github.com/lzl124631x
// Time: O(log(max(tx, ty)))
// Space: O(1)
// Ref: https://leetcode.com/problems/reaching-points/discuss/114856/JavaC%2B%2BPython-Modulo-from-the-End
class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (sx < tx && sy < ty) {
            if (tx < ty) ty %= tx;
            else tx %= ty;
        }
        return (sx == tx && sy <= ty && (ty - sy) % sx == 0)
            || (sy == ty && sx <= tx && (tx - sx) % sy == 0);
    }
};