Problem Description
Alice and Bob take turns playing a game, with Alice starting first. Initially, there are n stones in a pile. On each player's turn, that player makes a move consisting of removing any non-zero square number of stones in the pile. If a player cannot make a move, he/she loses the game. Given a positive integer n, return true if and only if Alice wins the game otherwise return false, assuming both players play optimally.
Key Insights
- Players can only remove square numbers of stones (1, 4, 9, 16, ...).
- If a player cannot make a move (i.e., there are no stones left), they lose.
- The game can be analyzed using dynamic programming to determine winning and losing positions.
- A position is winning if there is at least one move to a losing position for the opponent.
Space and Time Complexity
Time Complexity: O(n * sqrt(n))
Space Complexity: O(n)
Solution
The solution uses dynamic programming to determine whether the current player (Alice) can guarantee a win with optimal play. We maintain a boolean array dp where dp[i] indicates whether the player whose turn it is with i stones can win. We iterate through all possible numbers of stones from 1 to n, and for each position, we check all square numbers that can be removed. If removing a square number leads to a losing position for the opponent, then the current position is a winning position.