We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Stone Removal Game

Number: 3625

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Alice and Bob play a stone removal game starting with n stones. Alice always goes first and is required to remove exactly 10 stones on her first turn. Then, on each subsequent move, the current player must remove exactly 1 stone fewer than the number removed by the previous opponent. If a player cannot remove the required number of stones because there aren’t enough left, that player loses. Given the number of stones n (1 <= n <= 50), determine if Alice wins the game.

Key Insights

  • Alice must remove 10 stones initially. If n < 10, she cannot make her move and loses immediately.
  • Each subsequent move requires removing 1 fewer stone than the previous move.
  • The game continues until the number of remaining stones is less than the required removal count.
  • Since the maximal removal sequence is fixed and n is small (<= 50), the game can be simulated turn by turn without performance issues.

Space and Time Complexity

Time Complexity: O(1) since the number of moves is at most a fixed constant (10 moves at most for n <= 50). Space Complexity: O(1) as only a few variables are used for simulation.

Solution

We solve the problem by simulating each turn. Start with Alice’s required removal of 10 stones. After each successful move, subtract the required stones from n, decrease the removal count by 1, and toggle the player’s turn. The simulation stops when there are not enough stones to meet the removal requirement. The player who is unable to make the move loses and the other player is declared the winner. We use simple integer variables for n and the current move requirement, ensuring constant-space operations.

Code Solutions

# Function to determine if Alice wins the stone removal game

def stoneRemovalGame(n: int) -> bool:
    # starting move is 10 for Alice
    current_removal = 10
    # True means it's Alice's turn, False means Bob's turn
    alice_turn = True
    
    # Continue simulation as long as there are enough stones to remove
    while n >= current_removal:
        # Subtract the stones removed from the total
        n -= current_removal
        # Decrease the removal count for the next turn
        current_removal -= 1
        # Toggle the turn (if it was Alice, now Bob, and vice versa)
        alice_turn = not alice_turn
    
    # At the end of the loop, the player who was supposed to move cannot make the move
    # If it is Alice's turn, then she loses, return False. Otherwise, Alice wins.
    return not alice_turn

# Example usage:
print(stoneRemovalGame(12))  # Expected output: True
print(stoneRemovalGame(1))   # Expected output: False
← Back to All Questions