Code Implementation

class Solution:
    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:
                if ty > sy:
                    tx %= ty
                else:
                    # ty == sy, can only reach if (tx - sx) % ty == 0
                    return (tx - sx) % ty == 0
            else:
                if tx > sx:
                    ty %= tx
                else:
                    # tx == sx, can only reach if (ty - sy) % tx == 0
                    return (ty - sy) % tx == 0
        return False
      

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

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == sx && ty == sy) return true;
            if (tx > ty) {
                if (ty > sy)
                    tx %= ty;
                else
                    // ty == sy
                    return (tx - sx) % ty == 0;
            } else {
                if (tx > sx)
                    ty %= tx;
                else
                    // tx == sx
                    return (ty - sy) % tx == 0;
            }
        }
        return false;
    }
}
      

var reachingPoints = function(sx, sy, tx, ty) {
    while (tx >= sx && ty >= sy) {
        if (tx === sx && ty === sy) return true;
        if (tx > ty) {
            if (ty > sy)
                tx %= ty;
            else
                // ty == sy
                return (tx - sx) % ty === 0;
        } else {
            if (tx > sx)
                ty %= tx;
            else
                // tx == sx
                return (ty - sy) % tx === 0;
        }
    }
    return false;
};
      

Problem Description

Given four integers sx, sy, tx, and ty, you start from the point (sx, sy) and want to reach the point (tx, ty) using a series of moves. In each move, you can transform the current point (x, y) to either (x + y, y) or (x, y + x). Determine whether it is possible to reach (tx, ty) from (sx, sy) using only these moves.

• All coordinates are positive integers.
• You cannot reuse elements or undo moves.
• There may be only one valid solution or none at all.

Thought Process

At first glance, the problem seems to invite a brute-force or breadth-first search (BFS) approach: start at (sx, sy), generate all possible next positions, and check if you can reach (tx, ty). However, this quickly becomes infeasible as the numbers grow large, since the number of possibilities explodes exponentially.

The key insight is to notice the nature of the allowed moves: you can only add one coordinate to the other, and both coordinates are always increasing. Instead of searching forward, we can try to work backwards from (tx, ty) to (sx, sy), reversing the process. If you know the last move, you can subtract one coordinate from the other, as long as the result is still positive and at least as large as the starting coordinates.

This reversal is much more efficient, especially if we use modulo operations to "jump" directly to the relevant previous states, avoiding many unnecessary steps.

Solution Approach

• Reverse the Process: Instead of moving forward, we start from (tx, ty) and work backwards, subtracting the smaller coordinate from the larger.
• Use Modulo for Efficiency: If tx > ty, then the last move must have been to add ty to some previous x. Thus, the previous tx must have been tx - k * ty for some k, so we can set tx = tx % ty to skip directly to the possible previous state.
• Stop When Out of Bounds: If either tx or ty drops below sx or sy, it's impossible to reach (sx, sy).
• Handle Edge Cases: If either coordinate matches the start, check whether the other coordinate can be reduced to the start by repeated subtractions (i.e., whether the difference is divisible by the other coordinate).
• Return the Result: If we ever reach (sx, sy), return true; otherwise, return false.

This approach ensures we don't waste time exploring unnecessary states and makes the solution feasible even for large numbers.

Example Walkthrough

Let's consider the input: sx = 1, sy = 1, tx = 3, ty = 5.

1. Start at (tx, ty) = (3, 5).
2. Since 5 > 3, we subtract 3 from 5: (3, 2).
3. Now 3 > 2, subtract 2 from 3: (1, 2).
4. 2 > 1, subtract 1 from 2: (1, 1).
5. We have reached (sx, sy) = (1, 1).

At each step, we used the reverse of the allowed moves, and ultimately reached the starting point. Thus, it is possible to reach (3, 5) from (1, 1).

Time and Space Complexity

• Brute-force/BFS Approach: The number of states is potentially exponential in the size of tx and ty, making the time and space complexity O(2^{max(tx, ty)}), which is infeasible for large numbers.
• Optimized Reverse/Modulo Approach: Each iteration reduces either tx or ty significantly, often by a large factor due to the modulo operation. Thus, the number of iterations is O(log(max(tx, ty))). Space complexity is O(1) since we only use a constant amount of extra variables.

This makes the optimized approach very efficient even for large input values.

Summary

The "Reaching Points" problem is a great example of how reversing the direction of a problem and using mathematical insights (like modulo operations) can turn an exponential brute-force challenge into an efficient algorithm. By working backwards and skipping unnecessary steps, we can efficiently determine whether it is possible to reach the target point from the starting point using the allowed moves, even for very large numbers.