780 Reaching Points

780. Reaching Points

1. Question

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), returnTrueif and only if a sequence of moves exists to transform the point(sx, sy)to(tx, ty). Otherwise, returnFalse.

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, tywill all be integers in the range[1, 10^9].

2. Implementation

(1) BFS (TLE)

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) {
            return false;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {sx, sy});

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] curPoint = queue.remove();
                int x = curPoint[0], y = curPoint[1];

                if (x == tx && y == ty) {
                    return true;
                }

                if (x + y <= tx) {
                    queue.add(new int[] {x + y, y});
                }

                if (x + y <= ty) {
                    queue.add(new int[] {x, x + y});
                }
            }
        }
        return false;
    }
}

(2) Math

思路：看解析

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (sx < tx && sy < ty) {
            if (tx > ty) {
                tx %= ty;
            }
            else {
                ty %= tx;
            }
        }

        if (sx == tx) {
            return (ty - sy) % sx  == 0;
        }
        else if (sy == ty) {
            return (tx - sx) % sy == 0;
        }
        else {
            return false;
        }
    }
}

3. Time & Space Complexity

Math: 时间复杂度O(max(tx, ty)), 空间复杂度O(1)