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.
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. By caching the outcome for each number of stones i, we avoid recomputing the same state multiple times, drastically reducing the time complexity.
Algorithm
- Create a memoization array,
memo, of sizen + 1to store the results of subproblems. Initialize it with a value indicating that the state has not been computed (e.g.,null). - Define a helper function, say
canWin(n, memo). - Base case: If
n <= 0, returnfalse. - Memoization check: If
memo[n]is notnull, return the stored value. - Iterate through all possible moves by subtracting a square number
k*kfromn. - For each move, recursively call
canWin(n - k*k, memo). - If the recursive call returns
false, it means we found a winning move. Storetrueinmemo[n]and returntrue. - If the loop finishes without finding a winning move, store
falseinmemo[n]and returnfalse. - The main function initializes the memo array and calls the helper function.
Walkthrough
To optimize the brute-force recursion, we can use memoization. This technique stores the results of expensive function calls and returns the cached result when the same inputs occur again. We use an array, memo, to store the outcome (true for a win, false for a loss) for each number of stones from 0 to n.
Before computing the result for n stones, we first check if memo[n] has already been computed. If it has, we return the stored value immediately. Otherwise, we compute the result as in the recursive approach, and before returning, we store the result in memo[n]. This ensures that the subproblem for each number of stones is solved only once.
class Solution { public boolean winnerSquareGame(int n) { // Use Boolean array to distinguish between not computed (null), win (true), and loss (false). Boolean[] memo = new Boolean[n + 1]; return canWin(n, memo); } private boolean canWin(int n, Boolean[] memo) { if (n <= 0) { return false; } if (memo[n] != null) { return memo[n]; } // Try all possible moves. for (int k = 1; k * k <= n; k++) { // If there is a move to a state from which the opponent cannot win, we win. if (!canWin(n - k * k, memo)) { memo[n] = true; return true; } } // If all moves lead to a winning state for the opponent, we lose. memo[n] = false; return false; }}Complexity
Time
O(n * sqrt(n)). Each state `i` from 1 to `n` is computed only once. To compute the result for `i`, we iterate through `sqrt(i)` possible moves. The total work is the sum of `sqrt(i)` for `i` from 1 to `n`, which is bounded by `n * sqrt(n)`.
Space
O(n). This is for the memoization array of size `n+1` and the recursion stack, which can go up to depth `n` in the worst case.
Trade-offs
Pros
Significantly more efficient than brute-force.
Guaranteed to solve the problem within the time limits.
Still maintains a readable, recursive structure.
Cons
May cause a
StackOverflowErrorfor very largendue to deep recursion, although it's generally fine forn=10^5in most competitive programming environments.
This is an iterative dynamic programming approach that builds the solution from the smallest subproblem up to the target n. It uses a DP array where dp[i] stores whether the first player can win with i stones. This avoids recursion and the associated overhead and potential stack depth issues.
Algorithm
- Create a boolean DP array,
dp, of sizen + 1.dp[i]will betrueif the player starting withistones wins. dp[0]is implicitlyfalse(or can be explicitly set), as a player with 0 stones loses.- Iterate from
i = 1ton. - For each
i, determine the value ofdp[i]. Iterate through all possible movesk*k(wherek*k <= i). - Check the state the opponent would be in:
dp[i - k*k]. - If
dp[i - k*k]isfalse, it means the current player can force the opponent into a losing position. Therefore, the current player wins. Setdp[i] = trueand break the inner loop to move to the nexti. - If the inner loop completes and
dp[i]is stillfalse, it means all moves lead to a winning state for the opponent, so the current player loses. - After the outer loop finishes,
dp[n]holds the answer for the original problem.
Walkthrough
The bottom-up dynamic programming approach is an iterative alternative to the recursive solution. It solves the problem by building up a solution from smaller subproblems. We use a boolean array dp of size n + 1, where dp[i] represents whether the starting player can win with i stones.
We iterate from i = 1 to n. For each i, we determine dp[i]. A player can win with i stones if they can make a move (remove k*k stones) to a state i - k*k where the opponent loses. In our DP table, this corresponds to finding a k such that dp[i - k*k] is false. If such a move exists, we set dp[i] to true and move to the next i. If after checking all possible moves from i, we don't find any that lead to a losing state for the opponent, dp[i] remains false. The final answer is dp[n].
class Solution { public boolean winnerSquareGame(int n) { boolean[] dp = new boolean[n + 1]; // dp[0] is false by default, meaning a player with 0 stones loses. for (int i = 1; i <= n; i++) { // Check if there is any move to a losing position for the opponent. for (int k = 1; k * k <= i; k++) { if (!dp[i - k * k]) { // If opponent loses from state i - k*k, then we win from state i. dp[i] = true; break; // Found a winning move, no need to check further for this i. } } // If the inner loop completes without setting dp[i] to true, it remains false. } return dp[n]; }}Complexity
Time
O(n * sqrt(n)). The outer loop runs `n` times, and for each `i`, the inner loop runs `sqrt(i)` times. The total complexity is the sum of `sqrt(i)` for `i` from 1 to `n`.
Space
O(n) to store the DP array of size `n+1`.
Trade-offs
Pros
Highly efficient and avoids recursion overhead.
No risk of stack overflow errors.
Often slightly faster in practice than the memoized recursive solution.
Cons
Can be slightly less intuitive to write than the top-down recursive approach for some developers.
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; }}class Solution { public: bool winnerSquareGame ( int n ) { int f [ n + 1 ]; memset ( f , 0 , sizeof ( f )); function < bool ( int ) > dfs = [ & ]( int i ) -> bool { if ( i <= 0 ) { return false ; } if ( f [ i ] != 0 ) { return f [ i ] == 1 ; } for ( int j = 1 ; j <= i / j ; ++ j ) { if ( ! dfs ( i - j * j )) { f [ i ] = 1 ; return true ; } } f [ i ] = - 1 ; return false ; }; return dfs ( n ); } };class Solution : def winnerSquareGame ( self , n : int ) -> bool : @ cache def dfs ( i : int ) -> bool : if i == 0 : return False j = 1 while j * j <= i : if not dfs ( i - j * j ): return True j += 1 return False return dfs ( n )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.