Double or Subtract

Hard

A token stands at the point (1, 1) of an infinite grid. In one move a token at (x, y) can be moved to any of these points: - (x, y − x) - (x − y, y) - (2·x, y) - (x, 2·y) You are given goal_x and goal_y. Return True if the token can reach (goal_x, goal_y) in a finite number of moves, and False otherwise.

Example 1

goal_x=8, goal_y=24 → True

(1, 1) → (1, 2) → (1, 4) → (1, 3) → (2, 3) → (4, 3) → (8, 3) → (8, 6) → (8, 12) → (8, 24).

Example 2

goal_x=10, goal_y=15 → False

No sequence of moves ends at (10, 15).

Example 3

goal_x=12, goal_y=5 → True

Constraints

1 ≤ goal_x, goal_y ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Number Theory

Similar problems

Biggest Shared-Factor Group Hard Make One From Multiples Hard Towns Joined by Big Divisors Hard Nearest Coprime Ancestor Hard Prime Budget, Full Divisors Hard

Input

goal_x=8, goal_y=24

Expected

True

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