Scale Engineer

Reaching Points

Hard
#0734Time: O(2^(tx+ty)). The search space can be visualized as a binary tree. The depth of this tree can be on the order of `tx + ty`, leading to an exponential number of states to explore. This is computationally infeasible for the given constraints.Space: O(tx + ty). The space complexity is determined by the maximum depth of the recursion stack. In the worst case, the depth can be proportional to the sum of the target coordinates.7 companies
Patterns
Math
Companies
DocusignJ.P. MorganKLAWayfair

Prompt

Given four integers sx, sy, tx, and ty, return true if it is possible to convert the point (sx, sy) to the point (tx, ty) through some operations, or false otherwise.

The allowed operation on some point (x, y) is to convert it to either (x, x + y) or (x + y, y).

 

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a straightforward depth-first search (DFS) starting from the source point (sx, sy). We recursively explore the two possible moves from any point (x, y): (x, x + y) and (x + y, y). The search continues until we either reach the target point (tx, ty) or the current coordinates exceed the target coordinates, at which point that search path is abandoned.

Algorithm

  1. Define a recursive function solve(x, y, tx, ty).
  2. Base Case 1: If x == tx and y == ty, a path has been found, so return true.
  3. Base Case 2: If x > tx or y > ty, the current path has overshot the target. Since coordinates only increase, this path is invalid. Return false.
  4. Recursive Step: Explore the two possible next states:
    • Call solve(x + y, y, tx, ty).
    • Call solve(x, x + y, tx, ty).
  5. Return true if either of the recursive calls returns true, otherwise return false.

Walkthrough

The core idea is to model the problem as a state-space search. The starting state is (sx, sy). From any state (x, y), we can transition to two new states. We can implement this search using recursion.

A recursive function, say canReach(current_x, current_y), is defined to check if the target is reachable from the current point.

  • Base Cases:

    • If current_x == tx and current_y == ty, we have successfully reached the target. The function should return true.
    • If current_x > tx or current_y > ty, we have overshot the target. Since the coordinates only increase with each operation, this path is invalid. The function should return false to prune this branch of the search.

  • Recursive Step:

    • The function makes two recursive calls to explore both possible moves:
      1. canReach(current_x, current_x + current_y)
      2. canReach(current_x + current_y, current_y)
    • If either of these calls returns true, it means a valid path to the target exists, so the function propagates true up the call stack.
    • If both calls return false, no path exists from the current point, and the function returns false.

The initial call to start the search would be canReach(sx, sy).

class Solution {    public boolean reachingPoints(int sx, int sy, int tx, int ty) {        if (sx > tx || sy > ty) {            return false;        }        if (sx == tx && sy == ty) {            return true;        }        // Explore both possible moves        return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);    }}

Complexity

Time

O(2^(tx+ty)). The search space can be visualized as a binary tree. The depth of this tree can be on the order of `tx + ty`, leading to an exponential number of states to explore. This is computationally infeasible for the given constraints.

Space

O(tx + ty). The space complexity is determined by the maximum depth of the recursion stack. In the worst case, the depth can be proportional to the sum of the target coordinates.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correctly represents the problem's state transitions.

Cons

  • Extremely inefficient and will not pass for the given constraints.

  • Leads to a Time Limit Exceeded error on most platforms.

  • Can cause a StackOverflowError for paths that are very long, as the recursion depth can become very large.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem