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

Python3JavaC++GoTypeScript

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

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;
    }
};

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;
}

3360. Stone Removal Game

Description

Solutions

Solution 1: Simulation

Comments