Katkat
Back

Reach a Target Pair by Repeatedly Adding One Coordinate to the Other

Virtu FinancialQuantitative Researcher · Online Assessment
HardQuantitative ResearcherOnline AssessmentCoding & Algorithms

Last updated

Starting from a pair of positive integers, each move adds one coordinate to the other. Decide whether an exact target pair can be reached. Tests reasoning about reachability when values go up to one billion and simulating every forward move is far too slow.

You start with an ordered pair of positive integers (sx, sy). In one move you replace the current pair (x, y) with either (x, x + y) or (x + y, y).

Return whether some sequence of zero or more moves turns (sx, sy) into exactly (tx, ty).

Function Signature

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

Rules

  • The pair is ordered: (2, 3) and (3, 2) are different pairs.
  • Zero moves are allowed, so the answer is True whenever (sx, sy) == (tx, ty).
  • Return True if (tx, ty) is reachable and False otherwise.

Constraints

  • 1 <= sx, sy, tx, ty <= 10^9
  • All input values fit in a 32-bit signed integer.

Examples

Example 1

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True

One sequence is (1, 1) -> (1, 2) -> (3, 2) -> (3, 5).

Example 2

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Starting from (1, 1), the only reachable pairs with both coordinates at most 2 are (1, 1), (1, 2) and (2, 1).

Example 3

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True