PracHub
QuestionsCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Optiver

Stone Pile Doubling Game: Can One Pile Be Emptied?

Last updated: Jul 2, 2026

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.

Related Interview Questions

  • Build and Validate a Binary Tree from Parent-Child Pairs - Optiver (medium)
  • Days Between Two Calendar Dates - Optiver (medium)
  • Thread-Safe Stock Inventory: Buy and Sell Without Overselling - Optiver (medium)
  • Find missing numbers in sequences - Optiver (hard)
  • Design a circular queue data structure - Optiver (medium)
|Home/Coding & Algorithms/Optiver

Stone Pile Doubling Game: Can One Pile Be Emptied?

Optiver logo
Optiver
Jul 26, 2025, 12:00 AM
easyData ScientistTechnical ScreenCoding & Algorithms
0
0

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.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Optiver•More Data Scientist•Optiver Data Scientist•Optiver Coding & Algorithms•Data Scientist Coding & Algorithms
PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.