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 Game IV

Number: 1617

Difficulty: Hard

Paid? No

Companies: Microsoft

Problem Description

Alice and Bob play a game with n stones. On each turn, the current player removes any non-zero square number of stones from the pile. The player who cannot make a move loses. Given n, determine if Alice (starting first) can force a win if both play optimally.

Key Insights

  • Use Dynamic Programming (DP) where dp[i] indicates if the current player can win with i stones.
  • For each state i, iterate over all perfect square numbers j^2 that are <= i.
  • If there is any move that leads to a losing state for the opponent (dp[i - j^2] is false), then dp[i] becomes true.
  • Base case: dp[0] is false since with 0 stones, the current player loses.

Space and Time Complexity

Time Complexity: O(n * sqrt(n))
Space Complexity: O(n)

Solution

We use a bottom-up dynamic programming approach with an array dp of size n + 1. The dp array stores whether the current player can force a win when there are i stones remaining.

  • Initialize dp[0] = false since no stones mean loss.
  • For each number from 1 to n, check every perfect square number less than or equal to i.
  • If there exists a perfect square removal that leaves the opponent in a losing position, set dp[i] to true.
  • The final answer is dp[n].
    This solution leverages the fact that optimal substructure exists and that by simulating every valid move (each removal of a perfect square), we can determine the outcome for each state.

Code Solutions

# Python solution for Stone Game IV

def winnerSquareGame(n: int) -> bool:
    # dp[i] indicates if current player can win with i stones left
    dp = [False] * (n + 1)
    # Base case: With 0 stones, current player loses
    dp[0] = False
    
    # Iterate over all number of stones from 1 to n
    for i in range(1, n + 1):
        # Try all perfect squares j*j that are less or equal than i
        j = 1
        while j * j <= i:
            # If removing j*j stones leads to a losing state for the opponent,
            # then the current state i is winning
            if not dp[i - j * j]:
                dp[i] = True
                break  # No need to check further if winning move is found
            j += 1
    return dp[n]

# Example usage:
print(winnerSquareGame(1))  # Output: True
print(winnerSquareGame(2))  # Output: False
← Back to All Questions