Make Two Apple Piles Equal With Doubling Moves
Company: Optiver
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Company: Optiver
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You have two piles of apples: the first pile contains a apples and the second pile contains b apples.
In one move you choose one pile to be the receiving pile and move apples into it from the other pile. The number of apples moved must be exactly the number of apples the receiving pile currently contains, so the receiving pile doubles in size. A move is legal only if the giving pile holds at least that many apples.
Determine whether there is a finite sequence of moves after which both piles contain the same number of apples. Return true if it is possible (including when the piles are already equal), and false otherwise.
Function signature
canBalance(a, b) -> boolean
Input
a
— the number of apples in the first pile
b
— the number of apples in the second pile
Output
true
if the two piles can be made equal through some sequence of legal moves,
false
otherwise.
Constraints
1 <= a, b <= 10^9
Examples
a = 3, b = 5
→
true
Move 3 apples from the second pile onto the first:
(3, 5) → (6, 2)
. Then move 2 apples from the first pile onto the second:
(6, 2) → (4, 4)
. The piles are equal.
a = 1, b = 2
→
false
The reachable states cycle:
(1, 2) → (2, 1) → (1, 2) → ...
— the piles never become equal.
a = 2, b = 4
→
false
(2, 4) → (4, 2) → (2, 4) → ...
— the states repeat and equality is never reached.
a = 7, b = 7
→
true
The piles are already equal; zero moves are needed.