Welcome to Subscribe On Youtube
3360. Stone Removal Game
Description
Alice and Bob are playing a game where they take turns removing stones from a pile, with Alice going first.
- Alice starts by removing exactly 10 stones on her first turn.
- For each subsequent turn, each player removes exactly 1 fewer stone than the previous opponent.
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:
- Alice removes 10 stones on her first turn, leaving 2 stones for Bob.
- Bob cannot remove 9 stones, so Alice wins.
Example 2:
Input: n = 1
Output: false
Explanation:
- Alice cannot remove 10 stones, so Alice loses.
Constraints:
1 <= n <= 50
Solutions
Solution 1: Simulation
We simulate the game process according to the problem description until the game can no longer continue.
Specifically, we maintain two variables $x$ and $k$, representing the current number of stones that can be removed and the number of operations performed, respectively. Initially, $x = 10$ and $k = 0$.
In each round of operations, if the current number of stones that can be removed $x$ does not exceed the remaining number of stones $n$, we remove $x$ stones, decrease $x$ by $1$, and increase $k$ by $1$. Otherwise, we cannot perform the operation, and the game ends.
Finally, we check the parity of $k$. If $k$ is odd, Alice wins the game; otherwise, Bob wins the game.
The time complexity is $O(\sqrt{n})$, where $n$ is the number of stones. The space complexity is $O(1)$.
-
class Solution { public boolean canAliceWin(int n) { int x = 10, k = 0; while (n >= x) { n -= x; --x; ++k; } return k % 2 == 1; } } -
class Solution { public: bool canAliceWin(int n) { int x = 10, k = 0; while (n >= x) { n -= x; --x; ++k; } return k % 2; } }; -
class Solution: def canAliceWin(self, n: int) -> bool: x, k = 10, 0 while n >= x: n -= x x -= 1 k += 1 return k % 2 == 1 -
func canAliceWin(n int) bool { x, k := 10, 0 for n >= x { n -= x x-- k++ } return k%2 == 1 } -
function canAliceWin(n: number): boolean { let [x, k] = [10, 0]; while (n >= x) { n -= x; --x; ++k; } return k % 2 === 1; }