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

Quick Overview

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.

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

Company: Virtu

Role: Quantitative Researcher

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Online Assessment

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 ```python 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** ```text Input: sx = 1, sy = 1, tx = 3, ty = 5 Output: True ``` One sequence is `(1, 1) -> (1, 2) -> (3, 2) -> (3, 5)`. **Example 2** ```text 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** ```text Input: sx = 1, sy = 1, tx = 1, ty = 1 Output: True ```

Overview: 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)`. Implement `can_reach(sx, sy, tx, ty)`, which returns whether some sequence of zero or more moves turns `(sx, sy)` into exactly `(tx, ty)`: `True` if `(tx, ty)` is reachable and `False` otherwise (`true` / `false` in JavaScript, Java and C++). ### 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)`. ### Constraints - `1 <= sx, sy, tx, ty <= 10^9` - All input values fit in a 32-bit signed integer. The result is a boolean, so no value in this problem exceeds `2^31 - 1`; a 32-bit `int` is sufficient in Java and C++. ### Examples **Example 1** ```text Input: sx = 1, sy = 1, tx = 3, ty = 5 Output: True ``` One sequence is `(1, 1) -> (1, 2) -> (3, 2) -> (3, 5)`. **Example 2** ```text 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)`.

Constraints

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

Examples

Input: (1, 1, 1, 1)

Expected Output: True

Explanation: Minimum values; start equals target, so zero moves suffice.

Input: (1, 1, 3, 5)

Expected Output: True

Explanation: Example 1: (1, 1) -> (1, 2) -> (3, 2) -> (3, 5).

Hints

Each move changes exactly one coordinate and strictly increases it. What does that imply when a target coordinate is smaller than the matching start coordinate?
Ask which pairs could have produced (tx, ty) in a single move, given that both coordinates always stay positive.
Values reach 10^9, so applying moves one at a time can take far too many steps; look for a way to account for a long run of identical moves at once.

Approach

Work backward from the target. Every move keeps both coordinates positive and strictly increases exactly one of them, so after at least one move the two coordinates differ, and the larger one is the coordinate changed last. Hence a pair (x, y) with x > y has the single predecessor (x - y, y), a pair with y > x has the single predecessor (x, y - x), and a pair with x == y has none. The backward path from (tx, ty) is therefore unique, and the target is reachable exactly when that path passes through (sx, sy).

Algorithm: while tx > sx and ty > sy, replace the larger coordinate by its remainder modulo the smaller one (when tx == ty the remainder is 0 and the loop stops with an unreachable pair). This batches a run of identical backward steps: while, say, tx > ty and ty > sy, every intermediate pair (tx - k*ty, ty) still has y != sy, so none of them can be the start, and the path must continue until x drops below y. When the loop stops, at least one coordinate is no longer above its start value. If tx == sx and ty >= sy, x must stay fixed for the rest of the backward path, so only steps subtracting sx from y remain and the answer is whether ty - sy is a multiple of sx. Symmetrically, if ty == sy and tx >= sx, the answer is whether tx - sx is a multiple of sy. In every other case a coordinate fell below its start value (or the pair had equal coordinates), and the answer is False.

Edge cases: a start equal to the target returns True (0 is a multiple of anything); a target coordinate smaller than the start returns False immediately; equal target coordinates are reachable only with zero moves; the pair is ordered, so (tx, ty) and (ty, tx) can differ; checking only the gcd is insufficient because two coprime pairs can lie on different backward paths. All values stay within [0, 10^9], so 32-bit integers suffice. Each modulo step at least halves the reduced value, as in Euclid's algorithm, so the loop runs O(log(max(tx, ty))) times.

Time complexity:

O(log(max(tx, ty)))

Space complexity:

O(1)