1510. Stone Game IV
Problem Description
Alice and Bob are playing a turn-based game where they remove stones from a pile. The game begins with n
stones in the pile and in each turn, a player removes a square number of stones (like 1, 4, 9, 16, ...) from the pile. The players take alternate turns, with Alice always starting the game. The objective of the game is not to be the person who is unable to make a move (meaning that player can't remove a square number of stones because it doesn't exist in the pile). If a player can't make a move, they lose. The problem asks us to determine if Alice can win the game, assuming both Alice and Bob play optimally (making the best moves possible at every turn).
Intuition
To solve this game algorithmically, we can analyze it as a recursive problem, where each state of the game (the number of stones left in the pile) can lead to several possible next states (depending on which square number of stones is taken). The key insight is to recognize that the game has optimal substructure, meaning the optimal decision at a given state depends only on the states reachable from it and not on the path taken to reach that state. We can use dynamic programming to avoid recomputing the outcomes of these substates.
We want to determine if Alice can guarantee a win given n
stones. We can do this by simulating each player's moves recursively and memoizing (caching) the results to make the solution efficient. The base case of our recursive function is when there are 0 stones left, meaning the current player loses (since they can't make a move).
During Alice's turn (or Bob's), we check all possible moves (removing a square number of stones) and recursively call the function to simulate the opponent's turn with the remaining stones. If there's at least one move that leads Bob to a losing state (he can't force a win from that state), Alice wins by taking that move.
The dfs
function in the provided solution is a typical depth-first search with memoization (caching) that implements the above logic. The cache
decorator is used to memoize the results of the recursive calls, storing whether a particular number of stones leads to a win (True) or loss (False). During the recursion, if we find a state (number of stones) that makes the next player lose, we return True (indicating the current player can win).
In summary, we use depth-first search with memoization to check every possible move, remembering the outcomes of sub-problems to determine if Alice can win with n
starting stones.
Learn more about Math and Dynamic Programming patterns.
Solution Approach
The solution uses a recursive function that employs depth-first search (DFS) to explore the state space of the game and memoization to save the results of subproblems. Let's walk through the implementation as found above in the Solution
class:
-
The
winnerSquareGame
function is the starting point that takes an integern
, denoting the number of stones in the pile initially. -
It defines a nested function
dfs
which is a recursive function designed to return True if the current player can force a win withi
stones remaining, otherwise it returns False. -
The
dfs
function is decorated with@cache
from Python's standard library. This decorator automatically memoizes the results of thedfs
function to avoid recalculating the same subproblems. Memoization is a key feature that improves the efficiency of the solution by storing the outcome of each state after it is computed for the first time. -
Inside
dfs
, the base case is checked: ifi == 0
, the function returns False as the current player cannot make a move and thus loses. -
If the base case is not met, the function enters a loop to try all possible square number moves (
j * j
) that are less than or equal to the current stone count (i
). -
For each possible move, it performs a recursive call:
dfs(i - j * j)
. This call represents the next player's turn with the remaining stones after the current player removesj * j
stones. -
The key part of the logic is checking if
not dfs(i - j * j)
. If the result is True, this means that the opponent (next player) will lose in the state after the current move. Since the opponent loses, the current player wins, so the function returns True. -
If none of the potential moves lead to a winning state (the opponent can force a win no matter what the current player does), the loop finishes and the function returns False, indicating that the current player cannot force a win from this state.
-
Finally, the initial call
return dfs(n)
kicks off the recursive process for the initial state where Alice starts withn
stones.
The recursive depth-first search, coupled with memoization, is a classic dynamic programming approach, and it is very effective in this case for solving combinatorial game problems. The solution systematically explores all possible outcomes and is able to avoid redundant work thanks to the caching mechanism, making it feasible to compute the answer for larger values of n
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take n = 7
stones as an example to illustrate how the solution algorithm works. According to the rules, Alice can only take square numbers of stones - like 1, 4, or 9, and so on. Since we are concerned with the number 7, the only square numbers less than or equal to 7 are 1 (1x1) and 4 (2x2).
-
Alice starts the game and has the option to take 1 or 4 stones.
-
If Alice takes 1 stone, we're left with 6 stones. Now, it's Bob's turn. The recursive function (
dfs
) will try to determine if Bob can win given that 6 stones remain. -
If Alice takes 4 stones instead, 3 stones are left. Bob has only one choice here, which is to take 1 stone (as 4 is too many for the remaining 3), leaving 2 stones.
-
If at any point the
dfs
function is called with 0, it would return False, indicating the current player lost the game (as they can't make a move).
Let's trace the recursive calls from Alice's perspective when she takes 1 stone:
dfs(7)
- Alice's turn.- Alice takes 1:
dfs(6)
- Bob's turn.- Bob can take 1:
dfs(5)
- Alice's turn.- If Alice takes 1:
dfs(4)
- Bob's turn.- If Bob takes 1:
dfs(3)
- Alice's turn.- Alice will have no choice but to leave a losing state for Bob eventually, as none of the paths from this state lead to a win for her.
- If Bob takes 4:
dfs(0)
- Alice wins (Bob loses since no stones are left).
- If Bob takes 1:
- If Alice takes 4:
dfs(1)
- Bob's turn.- No matter what Bob does (taking 1), he leaves a win for Alice.
- If Alice takes 1:
- Bob can take 1:
- Alice takes 1:
From this example, with 7 stones, we can see that if Alice starts by taking 1 stone and at each step makes sure to leave a number of stones such that no square number can subtract to zero, she will win. The recursive calls will discover these winning strategies through its depth-first exploration, and the memoization will ensure we don't recompute the results for subproblems we've already seen.
Alice's winning strategy will look like this:
- Alice takes 1 (6 stones left).
- Bob could take 1 (5 stones left) or 4 (2 stones left).
- If 5 stones are left, Alice would take 4 (1 left), forcing Bob to take the last stone and lose.
- If 2 stones are left, Alice just needs to take 1, and Bob will be forced to take the last and lose.
By running through all possible scenarios like this, the algorithm concludes that Alice can win when the game starts with 7 stones.
Solution Implementation
1class Solution:
2 def winnerSquareGame(self, n: int) -> bool:
3 from functools import lru_cache
4
5 # Using memoization decorator to cache results of subproblems
6 @lru_cache(maxsize=None)
7 def can_win(remaining_stones: int) -> bool:
8 # A game state where no stones a left means a losing state
9 if remaining_stones == 0:
10 return False
11
12 square_root = 1
13 # Iterate through all possible square numbers less than or equal to the remaining stones
14 while square_root ** 2 <= remaining_stones:
15 # If the opponent loses in any following state, the current player wins
16 if not can_win(remaining_stones - square_root ** 2):
17 return True
18 square_root += 1
19
20 # If none of the moves lead to a win, then the current state is losing
21 return False
22
23 # Initiate the game with 'n' stones
24 return can_win(n)
25
1class Solution {
2 // This array is used for memoization to store the results of subproblems
3 private Boolean[] memo;
4
5 // This method starts the recursive depth-first search for finding the winner of the game
6 public boolean winnerSquareGame(int n) {
7 memo = new Boolean[n + 1]; // Initialize the memoization array
8 return dfs(n); // Start the recursive DFS from the given number 'n'
9 }
10
11 // This helper method performs the depth-first search to determine if the current player can win
12 private boolean dfs(int number) {
13 // Base case: if the number is 0, the current player can't make a move and thus loses
14 if (number <= 0) {
15 return false;
16 }
17 // Check if the result for the current number is already computed
18 if (memo[number] != null) {
19 return memo[number];
20 }
21 // Try all possible square numbers starting from 1 to the largest square number <= 'number'
22 for (int squareRoot = 1; squareRoot <= number / squareRoot; ++squareRoot) {
23 // Subtract the square of the current square root from 'number' to get the residual value
24 // Pass the residual value to the recursive call for the opponent's turn
25 int nextNumber = number - squareRoot * squareRoot;
26 if (!dfs(nextNumber)) {
27 // If the opponent loses on the residual value, the current player wins
28 return memo[number] = true;
29 }
30 }
31 // If after all attempts there's no winning strategy, the current player loses
32 return memo[number] = false;
33 }
34}
35
1class Solution {
2public:
3 bool winnerSquareGame(int n) {
4 // f represents the memoization array where
5 // 0 means uncomputed, 1 means current player can win, -1 means current player can't win
6 int memo[n + 1];
7 memset(memo, 0, sizeof(memo)); // Initialize memoization array to 0
8
9 // Define a recursive depth-first search function to determine if a player can win
10 function<bool(int)> dfs = [&](int remainingStones) -> bool {
11 if (remainingStones <= 0) { // Base case: no stones left
12 return false;
13 }
14 if (memo[remainingStones] != 0) { // If already computed, return the stored result
15 return memo[remainingStones] == 1;
16 }
17 // Try every square number less than or equal to the remaining stones
18 for (int squareRoot = 1; squareRoot * squareRoot <= remainingStones; ++squareRoot) {
19 // If the opponent can't win after the current player takes squareRoot^2 stones
20 if (!dfs(remainingStones - squareRoot * squareRoot)) {
21 memo[remainingStones] = 1; // Mark the current state as winning for the current player
22 return true; // The current player can force a win
23 }
24 }
25 memo[remainingStones] = -1; // Mark the current state as losing for the current player
26 return false; // The current player cannot force a win
27 };
28
29 // Call the dfs function with the total number of stones 'n' to determine if the player can win
30 return dfs(n);
31 }
32};
33
1// Determines if the player who starts with the game with 'n' stones is guaranteed to win.
2// A winning situation for any player occurs if they can force their opponent into a losing state.
3// In other words, if there's any move available that leaves the opponent with a combination of stones
4// that is already determined to be losing, the current player wins.
5function winnerSquareGame(stoneCount: number): boolean {
6 // Create an array to cache interim results where f[i] represents the winning
7 // condition for a game starting with i stones. Initialize all values to false.
8 const winningCache: boolean[] = new Array(stoneCount + 1).fill(false);
9
10 // Iterate over each possible number of stones.
11 for (let currentStoneCount = 1; currentStoneCount <= stoneCount; ++currentStoneCount) {
12 // Check every square number up to the current stone count.
13 for (let square = 1; square * square <= currentStoneCount; ++square) {
14 // If the current player can make a move that puts the opponent in a losing situation
15 // (winningCache[currentStoneCount - square * square] is false), then the current
16 // player is in a winning situation for currentStoneCount.
17 if (!winningCache[currentStoneCount - square * square]) {
18 winningCache[currentStoneCount] = true;
19 // As soon as a winning move is found, no need to check further moves.
20 break;
21 }
22 }
23 }
24 // Return the winning indication for the game starting with the original 'stoneCount'.
25 return winningCache[stoneCount];
26}
27
Time and Space Complexity
The given Python code aims to determine if a player can win a game where they can remove any square number of stones from a total of n
stones. The code uses a depth-first search (DFS) algorithm with memoization to prevent recomputing states that have already been solved. The memoization is implemented using the cache
decorator from Python's functools
.
Time Complexity
The time complexity of the solution depends on the number of distinct states i
that will be passed to the dfs
function and the number of iterations within each function call.
- Since each state from
n
to1
is computed only once due to memoization, there will ben
distinct states. - For each state
i
, the inner while loop runs forsqrt(i)
times since it enumerates through all possible square numbers that are less than or equal toi
.
Combining these factors, the overall time complexity of the recursive calls can be represented by the sum of square roots for all numbers from 1 to n
, which can be approximated by an integral from 1 to n
, resulting in O(n^(3/2))
.
Space Complexity
The space complexity of the solution includes the space used by the recursion stack and the memoization cache.
- The recursion stack will use
O(sqrt(n))
space since the maximum depth of recursion is limited by the maximum number of perfect squares you can subtract fromn
consecutively before reaching zero. - The memoization cache will hold a result for each state from
n
to1
, therefore requiringO(n)
space.
As a result, the overall space complexity is O(n)
because the cache dominates the space complexity due to storing the result for each state compared to the stack space in depth.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following uses divide and conquer strategy?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.