
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:
- Change it to
(x, x + y)
- 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)
.
- Initialize temporary variables
x
andy
with the values oftx
andty
. - Work backwards using a while loop until
x
andy
reduces or matches(sx, sy)
. For each iteration, determine:- If
x > y
, then reverse the operation(x + y, y)
by settingx
tox - y
. - If
y > x
, then reverse the operation(x, x + y)
by settingy
toy - x
. - If at any point during the reduction
x
matchessx
andy
matchessy
, return "true" indicating that transforming(sx, sy)
to(tx, ty)
is possible. - If
x
becomes less thansx
ory
becomes less thansy
before both values match the respective starting values, exit the loop.
- If
- After exiting the while loop, ensure whether both
x
andy
exactly matchsx
andsy
. 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
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 reducingtarget_x
by modulotarget_y
brings it closer tostart_x
. Iftarget_y
is already at its start point, check if the difference between the target and start forx
can be evenly divided bytarget_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.
No comments yet.