3360. Stone Removal Game

EasyMathSimulation

Problem Description

Alice and Bob are playing a game where they take turns removing stones from a pile, with Alice going first. The rules of the game are as follows:

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 on their turn.
The player who cannot make a move loses the game.

Given a positive integer n, representing the total number of stones, the task is to determine whether Alice wins the game. Return true if Alice wins and false otherwise.

Intuition

To solve this problem, we simulate the game's process in detail, based on the rules described:

Initialize x to 10, the number of stones Alice removes in her first turn, and k to 0, representing the number of completed operations.
In each turn, check if the current number of stones that can be removed (x) is less than or equal to the remaining number of stones (n). If so, perform the operation by:
- Decreasing n by x stones.
- Reducing x by 1 since the next player will remove one less stone.
- Incrementing k by 1 to signify a completed turn.
If x is greater than n at any point, the game ends as no more moves can be made.
After the loop, determine the winner:
- If k is odd, Alice's move was the last, so she wins.
- If k is even, Bob's move was the last, so he wins.

By simulating the game until a player cannot make a move, we can deduce the game's outcome based on the parity of k.

Learn more about Math patterns.

Solution Approach

The solution uses a straightforward simulation approach to model the game's progression. Here's a step-by-step breakdown of the implementation:

Initialization:
- Start with x = 10 as the number of stones Alice is supposed to remove in the first turn.
- Use k = 0 to track the number of completed operations (turns).
Simulate the Game:
- While the remaining stones n are sufficient to allow a player to make a move (i.e., n >= x):
  - Subtract x stones from n.
  - Decrease x by 1 to reflect the next move's stone count.
  - Increment k by 1 to log the operation.
Determine the Winner:
- Once no player can remove the required number of stones, the game ends.
- Check the parity of k:
  - If k % 2 == 1, Alice made the last valid move, implying she wins. Hence, return true.
  - If k % 2 == 0, Bob made the last move, and he wins, so return false.

The algorithm efficiently tracks the game's state through a series of simple arithmetic operations and checks, concluding with a decision based on the sequence of moves simulated.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example where the total number of stones n is 15 to illustrate the solution approach.

Initialization:
- Start with x = 10. Alice removes 10 stones initially.
- Initialize k = 0 to track the number of completed turns.
Simulate the Game:
- Turn 1:
  - Alice's move: Remove x = 10 stones.
  - Stones remaining (n): 15 - 10 = 5.
  - Decrease x by 1 for the next move, so x = 9.
  - Completed turns (k): k = 0 + 1 = 1.
- Turn 2:
  - Bob's move: Bob cannot remove 9 stones because only 5 stones remain; thus, x > n.
  - The game ends as no valid move can be made.
Determine the Winner:
- Check the parity of k (number of turns):
  - Since k % 2 == 1, Alice made the last valid move.
  - Alice wins, so return true.

In this example with n = 15, the simulation demonstrates that Alice wins by making the last feasible move.

Solution Implementation

1class Solution:
2    def canAliceWin(self, n: int) -> bool:
3        # Initialize x as 10 and the count k as 0
4        x = 10
5        k = 0
6      
7        # Reduce n by x until n is less than x
8        while n >= x:
9            n -= x  # Subtract x from n
10            x -= 1  # Decrease x by 1
11            k += 1  # Increment the count k by 1
12      
13        # Alice wins if the count k is odd
14        return k % 2 == 1
15

1class Solution {
2    /**
3     * Determines if Alice can win the game based on the given number n.
4     * 
5     * @param n the initial number for the game
6     * @return true if Alice can win, false if she cannot
7     */
8    public boolean canAliceWin(int n) {
9        int x = 10; // Defines the starting number to subtract from n
10        int k = 0;  // Counter for number of turns
11
12        // Loop until n is less than x
13        while (n >= x) {
14            n -= x; // Subtract x from n
15            x--;    // Decrease x by 1 for the next round
16            k++;    // Increment the number of turns
17        }
18
19        // If the number of turns, k, is odd, Alice wins
20        return k % 2 == 1;
21    }
22}
23

1class Solution {
2public:
3    bool canAliceWin(int n) {
4        int decrementValue = 10; // Starting decrement value
5        int movesCount = 0; // Keeps track of the number of moves
6
7        // Continue the loop until `n` is less than `decrementValue`
8        while (n >= decrementValue) {
9            n -= decrementValue; // Reduce `n` by `decrementValue`
10            --decrementValue; // Decrease `decrementValue` by 1
11            ++movesCount; // Increment the move counter
12        }
13
14        // If the number of moves is odd, Alice wins
15        return movesCount % 2 != 0;
16    }
17};
18

1// Function to determine if Alice can win a game with the given number n
2function canAliceWin(n: number): boolean {
3    // Initialize variables:
4    // x starts at 10, representing the initial decrement value
5    // k is a counter to track how many times x has been decremented
6    let [x, k] = [10, 0];
7
8    // Loop until n is less than x
9    // In each iteration, decrease n by x, decrease x by 1, and increase k by 1
10    while (n >= x) {
11        n -= x;  // Subtract the current value of x from n
12        --x;     // Decrease x by 1
13        ++k;     // Increase k by 1
14    }
15
16    // Return true if k is odd, false if k is even
17    return k % 2 === 1;
18}
19

Time and Space Complexity

The time complexity of the code is O(k), where k is the number of times the loop executes. Here, k increases with each iteration as long as n is greater than or equal to x. Since x decreases by 1 with each iteration, the loop roughly executes until 1 + 2 + ... + m ≈ n, which forms a triangular number equation leading to m = O(sqrt(n)). Hence, the time complexity is O(sqrt(n)).

The space complexity is O(1) since the algorithm uses a fixed amount of extra space regardless of the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: