Reaching Points

Updated on 08 July, 2025
Reaching Points header image

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

  • Java
java
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);
    }
}

The Java solution given defines a method isReachable to determine if it's possible to reach a target point (target_x, target_y) from a starting point (start_x, start_y) by incrementally adding the value of one coordinate to the other. The key operations used are modulo and conditional checks to navigate towards the starting point by reversing the steps:

  • Use a while loop to process until either target coordinate is less than its respective starting coordinate.
  • Break the loop if both target coordinates become equal, as this suggests a special edge condition that can't typically be resolved by simple additions from the starting point.
  • When target_x > target_y, assess if reducing target_x by modulo target_y brings it closer to start_x. If target_y is already at its start point, check if the difference between the target and start for x can be evenly divided by target_y.
  • Apply a similar logic when target_y > target_x.
  • Finally, confirm if both target coordinates have matched the starting coordinates exactly.

The implemented strategy uses mathematical reductions to backtrack from the target to the start efficiently, ensuring a solution is found or confirming impossibility within the given rules of navigation. This method doesn't handle any steps outwards from the start; instead, it aims to verify whether the target coordinates can be regressed to the start under the allowed operations.

Comments

No comments yet.