Stone Pile Doubling Game: Can One Pile Be Emptied?
Company: Optiver
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Company: Optiver
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given two piles of stones containing a and b stones respectively (both piles start non-empty).
You repeatedly apply the following move:
s
stones. Move exactly
s
stones from the larger pile to the smaller pile, so the smaller pile doubles in size.
For example, starting from piles (1, 24), one move yields (2, 23), the next yields (4, 21), then (8, 17), and so on. Note that the total number of stones never changes, and at every step the move is forced, so the entire process is determined by the starting pair.
Determine whether one of the piles will eventually become empty if you keep applying the move forever.
Return true if, after some finite number of moves, one pile contains zero stones. Return false if the process goes on forever without a pile ever becoming empty.
a
and
b
— the initial sizes of the two piles.
true
if some pile can be emptied,
false
otherwise.
1 <= a, b <= 10^9
a + b
; a step-by-step simulation of the process may take far too many moves to terminate within limits.
Example 1
Input: a = 3, b = 5
Output: true
Explanation: (3, 5) -> (6, 2) -> (4, 4) -> (8, 0). The second pile becomes empty after three moves.
Example 2
Input: a = 2, b = 6
Output: true
Explanation: (2, 6) -> (4, 4) -> (8, 0).
Example 3
Input: a = 1, b = 24
Output: false
Explanation: (1, 24) -> (2, 23) -> (4, 21) -> (8, 17) -> (16, 9) -> (7, 18) -> ... The pile sizes keep changing but eventually revisit an earlier state, so the process cycles forever and no pile is ever emptied.
Example 4
Input: a = 1, b = 23
Output: false
Explanation: (1, 23) -> (2, 22) -> (4, 20) -> (8, 16) -> (16, 8) -> (8, 16) -> ... The process enters the cycle (8, 16) -> (16, 8) and no pile is ever emptied. Starting from (1, 25) the process similarly cycles forever without emptying a pile.