Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8


Input: n = 1

Output: false

Explanation:

  * Alice cannot remove 10 stones, so Alice loses.

Constraints

  • 1 <= n <= 50

Solution

Method 1 - Simulate the Game

Intuition

Simulate the game turn by turn. Alice starts by removing 10 stones, then each player removes 1 less than the previous move. The player who cannot make a move loses.

Approach

  • Start with Alice’s turn, removing 10 stones.
  • Alternate turns, each time removing 1 less stone than the previous move.
  • If a player cannot remove the required number of stones, they lose.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    bool stoneGame(int n) {
        int turn = 0, remove = 10;
        while (n >= remove) {
            n -= remove;
            remove--;
            turn ^= 1;
        }
        return turn == 1; // If it's Alice's turn, she lost; if Bob's, Alice won
    }
};
1
2
3
4
5
6
7
8
9

func stoneGame(n int) bool {
    turn, remove := 0, 10
    for n >= remove {
        n -= remove
        remove--
        turn ^= 1
    }
    return turn == 1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public boolean stoneGame(int n) {
        int turn = 0, remove = 10;
        while (n >= remove) {
            n -= remove;
            remove--;
            turn ^= 1;
        }
        return turn == 1;
    }
}
1
2
3
4
5
6
7
8
9

fun stoneGame(n: Int): Boolean {
    var turn = 0; var remove = 10; var stones = n
    while (stones >= remove) {
        stones -= remove
        remove--
        turn = turn xor 1
    }
    return turn == 1
}
1
2
3
4
5
6
7

def stoneGame(n: int) -> bool:
    turn, remove = 0, 10
    while n >= remove:
        n -= remove
        remove -= 1
        turn ^= 1
    return turn == 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

pub fn stone_game(mut n: i32) -> bool {
    let mut turn = 0;
    let mut remove = 10;
    while n >= remove {
        n -= remove;
        remove -= 1;
        turn ^= 1;
    }
    turn == 1
}
1
2
3
4
5
6
7
8
9

function stoneGame(n: number): boolean {
    let turn = 0, remove = 10;
    while (n >= remove) {
        n -= remove;
        remove--;
        turn ^= 1;
    }
    return turn === 1;
}

Complexity

  • ⏰ Time complexity: O(1) (since the number of turns is at most 10)
  • 🧺 Space complexity: O(1)