Alice and Bob are playing a game where they take turns removing stones from a pile, with Alice going first.
The player who cannot make a move loses the game.
Given a positive integer n, return true if Alice wins the game and false otherwise.
Example 1:
Input: n = 12
Output: true
Explanation:
Example 2:
Input: n = 1
Output: false
Explanation:
Constraints:
1 <= n <= 50The Stone Removal Game is a typical game-theory style problem where two players take turns removing stones according to specific rules. Problems like this are often solved by identifying patterns in winning and losing states. Instead of simulating every possible move, you should observe how the number of stones changes after each valid operation and determine which states guarantee a win for the current player.
A straightforward approach is to simulate the turns while following the allowed removal rules. However, for an Easy level problem, a better strategy is usually to analyze small cases and detect a repeating pattern or mathematical property such as parity or modulo relationships. Once this pattern is identified, the winner can often be determined in constant time without running a full simulation.
This observation-based approach significantly reduces computation and leads to an efficient solution with minimal space usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Turn-by-turn Simulation | O(n) | O(1) |
| Mathematical / Pattern Observation | O(1) | O(1) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
The constraints are small enough that a brute-force solution is feasible.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, it falls under basic game theory concepts. Players alternate moves, and the goal is to determine whether the starting player can force a win by analyzing optimal strategies and state transitions.
Yes, variations of stone or coin removal games frequently appear in coding interviews. They test a candidate's ability to recognize patterns, reason about optimal play, and reduce simulations to simple mathematical rules.
Most solutions do not require complex data structures. Since the problem focuses on turn-based decisions and mathematical patterns, simple variables or counters are typically sufficient to determine the winner.
The optimal approach usually involves identifying patterns in winning and losing positions. By analyzing small cases and recognizing repeating states, the result can often be determined using a simple mathematical observation instead of full simulation.