Katkat
Back

Determine Whether One Point Can Reach Another

NVIDIASoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Determine whether a starting point (sx, sy) can reach a target (tx, ty) on a 2D integer grid via addition moves, optimized for coordinates up to 10^18.

Problem Statement

A point (x, y) on a 2D grid can transition to one of two valid adjacent points in a single step:

  1. (x + y, y)
  2. (x, x + y)

Given four positive integers sx, sy, tx, and ty, determine if it is possible to reach the target point (tx, ty) starting from (sx, sy) after zero or more moves.

Function Signature

def can_reach(sx: int, sy: int, tx: int, ty: int) -> bool:
    pass

Input

  • Four positive integers: sx, sy, tx, ty.

Output

  • Return True if (tx, ty) is reachable from (sx, sy), otherwise return False.

Constraints

  • `1 (1, 2) -> (3, 2) -> (3, 5)

#### Example 2

Input: sx = 1, sy = 1, tx = 2, ty = 2 Output: False Explanation: Moving from (1, 1) produces either (2, 1) or (1, 2). From either point, you can never reach (2, 2).


### Edge Cases to Consider
- Target is strictly smaller than the starting point along either axis (`tx < sx` or `ty < sy`).
- Target point is identical to the start point (`sx == tx` and `sy == ty`).
- Large differences between coordinates (e.g., `sx = 1, sy = 1, tx = 1, ty = 10^18`) where naive step-by-step subtraction will result in a Time Limit Exceeded (TLE).

Hints

Hint 1

Moving forward from (sx, sy) branches into two possibilities at every step, but moving backward from (tx, ty) is deterministic because both coordinates are positive.

Hint 2

Instead of subtracting the smaller coordinate from the larger coordinate repeatedly, consider using the modulo operator to skip repeated subtractions.

Hint 3

When one coordinate of the target matches the start (e.g., tx == sx), verify whether the difference between the other coordinates is a multiple of the matching coordinate.

Follow-up questions

  • What are the time and space complexities of your approach, and how does the time complexity relate to the Euclidean algorithm for GCD?
  • How would you modify your solution to return the minimum number of moves required to reach (tx, ty)?
  • How would the problem change if coordinates could be non-positive or if subtraction moves were also allowed?