Skip to content

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)\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public boolean canAliceWin(int n) {
        int x = 10, k = 0;
        while (n >= x) {
            n -= x;
            --x;
            ++k;
        }
        return k % 2 == 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    bool canAliceWin(int n) {
        int x = 10, k = 0;
        while (n >= x) {
            n -= x;
            --x;
            ++k;
        }
        return k % 2;
    }
};

1
2
3
4
5
6
7
8
9
func canAliceWin(n int) bool {
    x, k := 10, 0
    for n >= x {
        n -= x
        x--
        k++
    }
    return k%2 == 1
}

1
2
3
4
5
6
7
8
9
function canAliceWin(n: number): boolean {
    let [x, k] = [10, 0];
    while (n >= x) {
        n -= x;
        --x;
        ++k;
    }
    return k % 2 === 1;
}

Comments