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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Stone Removal Game

Difficulty: Easy

Problem 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.

Key Insights

  • Alice always starts by removing 10 stones.
  • The number of stones removed decreases by 1 for each player's turn.
  • The player unable to make a move (i.e., not enough stones left to remove) loses the game.
  • The game outcome can be determined by checking if the remaining stones after Alice's first turn leave Bob unable to play.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The solution relies on understanding the game mechanics and calculating the stones left after Alice's first move. If the remaining stones are less than 1 after Alice's turn, she wins; otherwise, we can simulate the turns until one player cannot remove the required number of stones. The algorithm uses basic arithmetic to determine the winner without needing to simulate every turn in detail.

Code Solutions

def stone_removal_game(n: int) -> bool:
    # Alice removes 10 stones initially
    n -= 10
    # If n is less than 1, Alice cannot make a move and loses
    if n < 1:
        return False
    # Simulate the game
    turn = 9  # Bob's first turn removes 9 stones
    while n >= turn:
        n -= turn
        turn -= 1  # Next turn the player removes one less stone
    return True  # If we exit the loop, Alice wins
← Back to All Questions