Solving the Problem Backwards: Leetcode 780 Reaching points

780. Reaching Points

The naive solution got TLE

100 / 190 test cases passed.
typedef pair<int, int> ii;
class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        queue<ii> Q;
        Q.emplace(sx, sy);
        set<ii> seen;
        seen.emplace(sx, sy);
        while (!Q.empty()) {
            auto [x, y] = Q.front(); Q.pop();
            if (x == tx && y == ty) return true;
            int x_plus_y = x + y;
            if (x_plus_y <= tx && !seen.count(make_pair(x_plus_y, y))) {
                Q.emplace(x_plus_y, y);
                seen.emplace(x_plus_y, y);
            }
            if (x_plus_y <= ty && !seen.count(make_pair(x, x_plus_y))) {
                Q.emplace(x, x_plus_y);
                seen.emplace(x, x_plus_y);
            }
        }
        return false;
    }
};

Solve it backward

Since our begin point can only be a number greater than 1, we can solve the problem backward. Detail can be seen from the following figure. A naive way to solve the problem backward, we still get TLE, although we can pass more test cases.

Image is from HERE

156 / 190 test cases passed.
class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > 0 && ty > 0) {
            if (tx == sx && ty == sy) return true;
            if (tx > ty) {
                tx -= ty;
            }
            else if (tx == ty) return false;
            else ty -= tx;
        }
        return false;
    }
};

This solution gets AC by introducing the mod operation

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > 0 && ty > 0) {
            if (tx == sx && ty == sy) return true;
            if (tx > ty) {
                if (sx < ty) tx %= ty;
                // tx will be greater than ty, we can not change ty, so we have to make sure ty == sy 
                else return (ty == sy && tx >= sx && (tx - sx) % ty == 0);
            }
            else if (tx == ty) return false;
            else {
                
                if (sy < tx) ty %= tx;
                // In order to make the following case can get passed, we have to add the ty >= sy 
                //  3, 7, 3, 4
                else return (tx == sx && ty >= sy && (ty - sy) % tx == 0);
            }
                
        }
        return false;
    }
};