Stone Game IV
HardPrompt
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.
Also, 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.
Example 1:
Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.Example 2:
Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).Example 3:
Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).
Constraints:
1 <= n <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the game's rules into a recursive function. A player wins if they can make a move that leaves the opponent in a losing state. The function recursively checks all possible moves (removing a square number of stones) to see if any lead to a losing position for the opponent.
Algorithm
- Define a recursive function, say
winnerSquareGame(n). - The base case is
n = 0, where the current player cannot move and loses. Returnfalse. - Iterate through all possible moves by subtracting a square number
k*kfromn, where1 <= k*k <= n. - For each possible next state
n - k*k, recursively callwinnerSquareGame(n - k*k). - If the recursive call returns
false, it means the opponent will be in a losing position. Thus, the current player wins. Returntrueimmediately. - If the loop completes without finding any such move, it means all moves lead to a winning position for the opponent. The current player loses. Return
false.
Walkthrough
This approach is a direct implementation of the recursive game theory logic. The core idea is that a player wins from a state n if they can make a move (subtracting k*k stones) to a state n - k*k from which the other player is guaranteed to lose. The function winnerSquareGame(n) checks this by trying every possible move. If any move leads to a state where the opponent loses (i.e., a recursive call returns false), the current player wins. If all moves lead to states where the opponent wins, the current player loses. This method is too slow because it re-calculates the result for the same number of stones multiple times, leading to an exponential number of calls.
// This solution will result in Time Limit Exceeded.class Solution { public boolean winnerSquareGame(int n) { if (n == 0) { return false; } for (int k = 1; k * k <= n; k++) { if (!winnerSquareGame(n - k * k)) { return true; } } return false; }}Complexity
Time
O(2^n) in the worst case. The recursion tree can grow exponentially as each call to `winnerSquareGame(n)` can result in up to `sqrt(n)` recursive calls. This leads to a massive number of redundant computations for the same subproblems.
Space
O(n) for the recursion stack depth in the worst-case scenario (e.g., when only 1 stone is removed at each step).
Trade-offs
Pros
Simple to conceptualize and implement.
Directly models the logic of the game.
Cons
Extremely inefficient due to repeated calculations of the same subproblems.
Not feasible for the given constraints (n <= 10^5) and will result in a Time Limit Exceeded error.
Solutions
Solution
class Solution {private Boolean[] f;public boolean winnerSquareGame(int n) { f = new Boolean[n + 1]; return dfs(n); }private boolean dfs(int i) { if (i <= 0) { return false; } if (f[i] != null) { return f[i]; } for (int j = 1; j <= i / j; ++j) { if (!dfs(i - j * j)) { return f[i] = true; } } return f[i] = false; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.