Stone Pile Doubling Game: Can One Pile Be Emptied?
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:
- Let the smaller pile contain `s` stones. Move exactly `s` stones from the larger pile to the smaller pile, so the smaller pile doubles in size.
- If the two piles are equal, move all stones from either pile to the other (the source pile then becomes empty). Both choices lead to the same pair of pile sizes, so the outcome is unchanged.
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.
### Input
- Two integers `a` and `b` — the initial sizes of the two piles.
### Output
- A boolean: `true` if some pile can be emptied, `false` otherwise.
### Constraints
- `1 <= a, b <= 10^9`
- The intended solution should run in time logarithmic in `a + b`; a step-by-step simulation of the process may take far too many moves to terminate within limits.
### Examples
**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.
Quick Answer: This question evaluates a candidate's algorithmic reasoning and discrete-mathematics skills, particularly understanding deterministic state transitions, invariants, and cycle detection in iterative processes.
You are given two piles of stones containing `a` and `b` stones respectively (both piles start non-empty).
You repeatedly apply the following move:
- Let the smaller pile contain `s` stones. Move exactly `s` stones from the larger pile to the smaller pile, so the smaller pile doubles in size.
- If the two piles are equal, move all stones from either pile to the other (the source pile then becomes empty). Both choices lead to the same pair of pile sizes, so the outcome is unchanged.
The total number of stones never changes, and at every step the move is forced, so the entire process is fully 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.
### Input
- Two integers `a` and `b` — the initial sizes of the two piles.
### Output
- A boolean: `true` if some pile can be emptied, `false` otherwise.
### Constraints
- `1 <= a, b <= 10^9`
- The intended solution runs in time logarithmic in `a + b`; a step-by-step simulation may take far too many moves to terminate within limits.
### Examples
**Example 1** — `a = 3, b = 5` -> `true`. `(3, 5) -> (6, 2) -> (4, 4) -> (8, 0)`.
**Example 2** — `a = 2, b = 6` -> `true`. `(2, 6) -> (4, 4) -> (8, 0)`.
**Example 3** — `a = 1, b = 24` -> `false`. The pile sizes keep changing but revisit an earlier state, so the process cycles forever.
**Example 4** — `a = 1, b = 23` -> `false`. The process enters the cycle `(8, 16) -> (16, 8)` and no pile is ever emptied.
Constraints
- 1 <= a, b <= 10^9
- Both piles start non-empty
- Solution should run in time logarithmic in a + b (no step-by-step simulation)
Examples
Input: (3, 5)
Expected Output: True
Explanation: n=8=2^3, odd part q=1 divides 3. Trace: (3,5)->(6,2)->(4,4)->(8,0).
Input: (2, 6)
Expected Output: True
Explanation: n=8, q=1 divides 2. Trace: (2,6)->(4,4)->(8,0).
Hints
- The total n = a + b never changes. A pile can only reach zero from an equal state (n/2, n/2), so the real question is whether the process ever hits equal piles.
- Track just ONE pile's count x modulo n. Check each of the three cases (x smaller, x larger, x equal) and you'll find every forced move sends x -> 2x (mod n).
- After t moves the tracked pile holds 2^t * a (mod n). It empties iff 2^t * a === 0 (mod n) for some t. Split n into its powers of two times its odd part q — the condition collapses to: q divides a.
- Concretely: strip all factors of 2 from a + b to get the odd part q, then return a % q == 0.