Show problems as
Classic problem #780HardMathEuclidean AlgorithmGreatest Common Divisor

Reaching Points

Real-world version: Growing a Pair by Adding One to the Other
Tracked in this browser only
Read Reaching Points on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pair of whole numbers starts as (sx, sy). One step replaces the pair either by its first number plus its second alongside the second, or by the first alongside the first plus the second.

Return true when some sequence of steps turns the starting pair into (tx, ty).

Examples

Example 1

Input
sx = 1, sy = 1, tx = 3, ty = 2
Output
true

From 1 and 1, growing the second gives 1 and 2, then growing the first gives 3 and 2.

Example 2

Input
sx = 1, sy = 1, tx = 2, ty = 2
Output
false

Any step from 1 and 1 makes the two numbers different, and no later step can bring them level again, so an equal pair is out of reach.

Example 3

Input
sx = 2, sy = 2, tx = 4, ty = 2
Output
true

Growing the first number by the second takes 2 and 2 straight to 4 and 2.

Constraints

  • 1 <= sx <= 10^9
  • 1 <= sy <= 10^9
  • 1 <= tx <= 10^9
  • 1 <= ty <= 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def reaching_points(sx: int, sy: int, tx: int, ty: int) -> bool:
Java
public boolean reachingPoints(int sx, int sy, int tx, int ty)

More on the same topics