Solution Explanation

This problem asks whether it's possible to reach a target point (tx, ty) from a starting point (sx, sy) using only two operations: (x, y) -> (x, x+y) or (x, y) -> (x+y, y). The solution employs a clever reverse-engineering approach.

Core Idea: Instead of trying to find a path from (sx, sy) to (tx, ty), the solution works backward from (tx, ty) towards (sx, sy). This is much more efficient than a brute-force forward approach, which could explore a vast number of possibilities.

Algorithm:

1. Base Cases: If sx == tx and sy == ty, we've reached the starting point, so return true.

2. Reverse Iteration: The algorithm iteratively reduces tx and ty using the modulo operator (%). The logic is based on the reverse of the allowed operations:

   • If tx > ty, it implies the last operation must have been (x, y) -> (x, x+y) where x = ty. Therefore, tx is updated to tx % ty. (We're effectively undoing that step).

   • Similarly, if ty > tx, the last operation was (x, y) -> (x+y, y) where y=tx. ty is updated to ty % tx.

3. Boundary Conditions: The loop continues until either:

   • tx <= sx or ty <= sy. This means we've gone as far back as possible, and it's time to check if we can reach the starting point from this point.
   • tx == ty is reached, it means we've reached a point where the only possible operations will not bring us closer to the sx, sy point.

4. Final Check: After the loop, there are three possible scenarios:

   • tx == sx && ty == sy: We've successfully reached the starting point, return true.
   • tx == sx: Check if we can reach sy from ty using only the operation (x,y) -> (x, x+y). This means ty - sy must be a multiple of tx.
   • ty == sy: Check if we can reach sx from tx using only the operation (x,y) -> (x+y, y). This means tx - sx must be a multiple of ty.
   • Otherwise, we couldn't reach the starting point, so return false.

Time Complexity: O(log(max(tx, ty))), because each iteration in the while loop roughly halves the maximum of tx and ty. The modulo operation effectively reduces the larger coordinate in each step.

Space Complexity: O(1), because the algorithm uses only a constant amount of extra space.

Code Examples (Python):

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while tx > sx and ty > sy:
            if tx > ty:
                tx %= ty
            else:
                ty %= tx
        return tx == sx and (ty - sy) % sx == 0 or ty == sy and (tx - sx) % sy == 0
 

This Python code directly implements the algorithm described above. The other languages (Java, C++, Go) follow the same logic with only syntactic differences.