Two Counters Built by Addition

Hard

A scoreboard shows two counters, currently holding a and b. In one move you add the value of one counter to the other: the pair (p, q) becomes either (p + q, q) or (p, p + q). Return True if some number of moves (possibly zero) turns the counters into the pair (x, y), in exactly that order, and False otherwise.

Example 1

a=2, b=3, x=8, y=11 → True

(2, 3) → (5, 3) → (8, 3) → (8, 11).

Example 2

a=1, b=2, x=4, y=4 → False

Every move leaves one number strictly larger than the other, so two equal numbers can only be had if you started with them.

Example 3

a=3, b=5, x=3, y=5 → True

Constraints

1 ≤ a, b, x, y ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math

Similar problems

The K-th Ordering of Digits Hard Stars on One Straight Line Hard Plus-Minus Calculator With Brackets Hard How Many Ones Are Written Hard Amount in Words Hard

Input

a=2, b=3, x=8, y=11

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.