We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reaching Points

Number: 796

Difficulty: Hard

Paid? No

Companies: Cloudflare, KLA, Goldman Sachs, Amazon, J.P. Morgan, Salesforce, Uber, Docusign, Workday, Coursera, Google

Problem Description

Given a starting point (sx, sy) and a target point (tx, ty), determine if it is possible to reach the target by repeatedly applying one of the two operations: (x, y) → (x, x+y) or (x, y) → (x+y, y).

Key Insights

  • Instead of building up from (sx, sy) forwards, work backwards from (tx, ty) by reversing the operations.
  • When both target coordinates are greater than the starting coordinates, you can use modulo arithmetic: subtract the smaller coordinate multiple times from the larger coordinate.
  • After reducing one coordinate below or equal to the corresponding starting coordinate, check if the remaining difference is a valid multiple.
  • Edge-case handling is critical when one coordinate exactly equals the starting coordinate.

Space and Time Complexity

Time Complexity: O(log(max(tx, ty))) – each loop iteration reduces one coordinate significantly using modulo. Space Complexity: O(1) – only a constant amount of extra space is used.

Solution

The solution works by reversing the allowed operations. Given (tx, ty), if both coordinates are larger than (sx, sy), then:

  • If tx > ty, observe that the previous step might have been (tx - ty, ty). Instead of subtracting ty repeatedly, we can compute tx % ty.
  • If ty > tx, compute ty % tx. Once one of the coordinates equals the starting coordinate, verify that the other coordinate can be reached by repeatedly adding the fixed coordinate. This check uses simple modular arithmetic. This backward approach is efficient given the problem constraints and avoids the exponential blowup that a recursive forward search would cause.

Code Solutions

# Python solution with line-by-line comments
def reachingPoints(sx, sy, tx, ty):
    # Loop while both target coordinates are strictly greater than the starting coordinates.
    while tx > sx and ty > sy:
        # If tx is greater than ty, the previous move should have been a reduction from tx using ty.
        if tx > ty:
            tx %= ty  # Instead of subtracting ty repeatedly, use modulo for efficiency.
        else:
            # Similarly, if ty is greater than tx, reduce ty by modulo operation.
            ty %= tx
    # If we have reduced tx to equal sx, check if the remaining difference in y can be covered by adding sx repeatedly.
    if tx == sx:
        return (ty - sy) % sx == 0 and ty >= sy
    # If we have reduced ty to equal sy, check if the remaining difference in x can be covered by adding sy repeatedly.
    if ty == sy:
        return (tx - sx) % sy == 0 and tx >= sx
    # If neither condition is met, the target cannot be reached.
    return False

# Example usage:
print(reachingPoints(1, 1, 3, 5))  # Expected output: True
← Back to All Questions