Reaching Points

Problem Statement

The goal of the problem is to determine whether it is possible to transform a starting coordinate point (sx, sy) to a target coordinate point (tx, ty) using a defined set of operations. These operations involve adding the value of one coordinate to the other. Specifically, for any point (x, y), you can either:

1. Change it to (x, x + y)
2. Change it to (x + y, y)

The task is to check if by repeatedly applying these operations starting from (sx, sy), we can ever reach the point (tx, ty).

Examples

Example 1

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)

Example 2

Input:

sx = 1, sy = 1, tx = 2, ty = 2

Output:

false

Example 3

Input:

sx = 1, sy = 1, tx = 1, ty = 1

Output:

true

Constraints

• 1 <= sx, sy, tx, ty <= 109

Approach and Intuition

Given that complex transformations could be required to move from (sx, sy) to (tx, ty), an intuitive way to analyze the problem could be to work backwards from (tx, ty) to (sx, sy), undoing the operations. This is because, at each step, the manipulation is more restrictive (specifically, subtraction rather than addition), which can simplify parsing the feasibility of reaching (sx, sy) from (tx, ty).

1. Initialize temporary variables x and y with the values of tx and ty.
2. Work backwards using a while loop until x and y reduces or matches (sx, sy). For each iteration, determine:
   • If x > y, then reverse the operation (x + y, y) by setting x to x - y.
   • If y > x, then reverse the operation (x, x + y) by setting y to y - x.
   • If at any point during the reduction x matches sx and y matches sy, return "true" indicating that transforming (sx, sy) to (tx, ty) is possible.
   • If x becomes less than sx or y becomes less than sy before both values match the respective starting values, exit the loop.
3. After exiting the while loop, ensure whether both x and y exactly match sx and sy. If they do, print "true", otherwise, "false".

This approach leverages the constraints effectively to reduce the problem complexity and check feasibility in a direct and efficient manner. By evaluating the problem from the end state back to the initial state, we can make a clear decision on the possibility of achieving the transformation under the given operations.

Solutions

class Solution {
    public boolean isReachable(int start_x, int start_y, int target_x, int target_y) {
        while (target_x >= start_x && target_y >= start_y) {
            if (target_x == target_y) break;
            if (target_x > target_y) {
                if (target_y > start_y) target_x %= target_y;
                else return (target_x - start_x) % target_y == 0;
            } else {
                if (target_x > start_x) target_y %= target_x;
                else return (target_y - start_y) % target_x == 0;
            }
        }
        return (target_x == start_x && target_y == start_y);
    }
}