LeetCode 1510 - Stone Game IV

LeetCode Problem 1510

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming, Game Theory

Solution

Problem Understanding

This problem is a two-player combinatorial game problem where Alice and Bob alternately remove stones from a single pile. On each turn, a player may remove any positive number of stones that is a perfect square (1, 4, 9, 16, etc.) as long as that number does not exceed the current pile size. The game ends when a player cannot make a move, which happens when the pile is empty; that player loses. Alice always moves first.

The input n represents the initial number of stones in the pile. The output is a boolean indicating whether Alice can guarantee a win if both players play optimally.

The constraints (1 <= n <= 10^5) suggest that naive recursive approaches that examine all move sequences will likely be too slow. The problem requires considering optimal play, which makes it a natural fit for dynamic programming. Edge cases include very small values of n such as 1 or perfect squares, which can result in an immediate win for Alice, as well as situations where n is not a perfect square and only suboptimal moves exist.

Approaches

Brute Force

The brute-force solution considers all possible sequences of moves recursively. For a given pile size n, we would try removing all square numbers less than or equal to n and recursively check if the resulting state is a losing position for the next player. If any resulting move leads to a losing position for the opponent, the current player wins.

This approach is correct because it explores the full game tree and respects optimal play. However, the time complexity is exponential, as each position can branch into multiple possible moves, making it infeasible for n up to 10^5.

Optimal Approach

The key observation is that this is a dynamic programming problem where each state depends on smaller subproblems. Define dp[i] as True if the current player can guarantee a win with i stones. For each i, check all square numbers s such that s <= i. If there exists any s where dp[i - s] is False (meaning the opponent loses after this move), then dp[i] is True. Otherwise, dp[i] is False.

This dynamic programming approach reduces the redundant computation of overlapping subproblems and is efficient enough for the given constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively explores all move sequences, exponential runtime
Optimal	O(n * √n)	O(n)	Uses DP to build winning states up to n, checking all square moves

Algorithm Walkthrough

1. Initialize a boolean array dp of size n + 1 with all values False. Here, dp[i] represents whether the current player can force a win with i stones.
2. Set dp[0] = False because if there are zero stones, the current player cannot move and loses.
3. Iterate i from 1 to n representing the current pile size.
4. For each i, iterate through all perfect squares s such that s <= i (e.g., 1, 4, 9, ...). You can compute this efficiently using s = k * k for k = 1 up to sqrt(i).
5. If for any s, dp[i - s] == False, then dp[i] = True. This indicates that the current player can make a move that leaves the opponent in a losing position.
6. After filling the dp array, return dp[n] as the result, which tells whether Alice (the first player) can force a win.

Why it works: The dynamic programming relies on the invariant that a position is winning if at least one move can leave the opponent in a losing position. This ensures correctness because the recursive dependency on smaller piles has been fully accounted for.

Python Solution

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [False] * (n + 1)
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                if not dp[i - j * j]:
                    dp[i] = True
                    break
                j += 1
        return dp[n]

In this implementation, we first create a DP array where each index i stores whether the player whose turn it is can win with i stones. We iterate from 1 to n and check all perfect square moves j*j. If any move leads to a losing state for the opponent (dp[i - j*j] == False), we mark dp[i] as True and break the loop, since one winning move is sufficient. Finally, dp[n] gives the answer for Alice.

Go Solution

func winnerSquareGame(n int) bool {
    dp := make([]bool, n+1)
    for i := 1; i <= n; i++ {
        for j := 1; j*j <= i; j++ {
            if !dp[i - j*j] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

The Go solution mirrors the Python approach. A boolean slice dp stores winning positions. Iterating over all perfect squares j*j up to i, we set dp[i] to true if any move leaves the opponent with a losing position. Go’s slices naturally initialize to false, so no explicit initialization is needed beyond make.

Worked Examples

Example 1: n = 1

i	j	dp[i - j*j]	dp[i]
1	1	dp[0] = False	True

Alice removes 1 stone and wins immediately.

Example 2: n = 2

i	j	dp[i - j*j]	dp[i]
1	1	False	True
2	1	dp[1] = True	False

Alice cannot leave Bob in a losing state, so she loses.

Example 3: n = 4

i	j	dp[i - j*j]	dp[i]
1	1	False	True
2	1	True	False
3	1	False	True
4	1	dp[3] = True	-
4	2	4 -> 0, dp[0] = False	True

Alice can remove all 4 stones and win immediately.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * √n)	For each of n positions, we iterate over all square numbers ≤ i (~√i), giving O(n√n)
Space	O(n)	We store the DP array of size n + 1

The main computational cost comes from iterating over possible moves for each pile size. The DP array is linear in size and sufficient to store the results of all subproblems.

Test Cases

# Provided examples
assert Solution().winnerSquareGame(1) == True  # Alice wins immediately
assert Solution().winnerSquareGame(2) == False # Alice cannot force a win
assert Solution().winnerSquareGame(4) == True  # Alice removes all stones

# Edge cases
assert Solution().winnerSquareGame(17) == True  # 17 -> 16 (square) -> leaves 1, Alice can win
assert Solution().winnerSquareGame(100000) == True  # large input stress test
assert Solution().winnerSquareGame(7) == False # Alice cannot force a win
assert Solution().winnerSquareGame(10) == True # Alice removes 1 or 4, forces a win
assert Solution().winnerSquareGame(0) == False # empty pile, Alice loses

Test	Why
n = 1	Smallest non-zero input, immediate win
n = 2	Small input where first player cannot win
n = 4	Perfect square, immediate win
n = 17	Non-trivial scenario with multiple squares
n = 100000	Maximum input stress test
n = 7	Alice cannot force a win
n = 10	Alice can force a win through optimal play
n = 0	Edge case of empty pile

Edge Cases

The first edge case is the smallest possible pile, n = 1. Alice can always win because 1 is a perfect square. The algorithm handles this correctly because dp[1] will immediately be set to True.

The second edge case is when n itself is a perfect square, like n = 4 or n = 9. Alice can remove all stones in one move. The implementation correctly iterates through squares and sets dp[n] = True if dp[n - s] = False, which includes the case n - s = 0.

The third edge case is non-trivial piles where Alice cannot win, such as `n =