Vivek's Blog

LeetCode 1510

A game theory problem that looks intimidating until you realize it's just a disguised DP — figure out who wins when both players play optimally.

Difficulty: Hard | Topics: DP, Math, Game Theory | Pattern: Win/Lose States

The Problem

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 from the pile (1, 4, 9, 16, 25...).

If a player is unable to make a move, they lose.

Given a positive integer n, return true if Alice wins the game, or false if Bob wins, assuming both play optimally.

Constraints: 1 <= n <= 10^5

Walking Through Examples

n = 1 Alice takes the only stone (1² = 1). Bob has none left and can't move. Alice wins → true

n = 2 Alice's only option is to remove 1 stone, leaving 1 for Bob. Bob removes that last stone. Alice has none left. Bob wins → false

n = 4 Alice removes all 4 stones at once (2² = 4). Bob has nothing left to remove. Alice wins → true

n = 4 is the trap. It's tempting to assume a perfect square always means the first player wins outright — that stops being true once n gets larger, because the opponent's replies matter too.

The Key Idea

Strip away the "Alice vs Bob" framing. At any pile size i, whoever's turn it is either wins or loses from that state, and that outcome doesn't depend on whose name is on it — only on i. So define one boolean per pile size:

dp[i] = true, if the player about to move with i stones left can force a win

dp[0] is false — a player facing 0 stones has no move and loses. For any i > 0, the current player wins if there exists some square j*j <= i that leaves the opponent in a losing state:

dp[i] = OR over all j*j <= i of ( NOT dp[i - j*j] )

The answer to the whole problem is just dp[n]. Every approach below computes the same recurrence — the difference is only in how the subproblems get evaluated.

1. Brute Force

Try every legal move from n, recurse into the remaining pile, and check if the opponent loses from there. No memory of subproblems already solved.

Time: exponential — the same sub-piles get recomputed from scratch on every path Space: O(√n) recursion depth

C++

bool solve(int n) {
    if (n == 0) return false;
    for (int i = 1; i * i <= n; i++)
        if (!solve(n - i * i)) return true;
    return false;
}
 
bool winnerSquareGame(int n) {
    return solve(n);
}

Java

class Solution {
    public boolean winnerSquareGame(int n) {
        return solve(n);
    }
    private boolean solve(int n) {
        if (n == 0) return false;
        for (int i = 1; i * i <= n; i++)
            if (!solve(n - i * i)) return true;
        return false;
    }
}

Python

def winner_square_game(n: int) -> bool:
    def solve(n):
        if n == 0:
            return False
        i = 1
        while i * i <= n:
            if not solve(n - i * i):
                return True
            i += 1
        return False
    return solve(n)

This times out well before n gets anywhere near LeetCode's limit of 10⁵. Useful mainly to confirm the recurrence is right on small inputs before optimizing.

2. Better: Top-Down with Memoization

Same recursion, but each pile size is only ever solved once. Store the result the first time you compute dp[i] and reuse it instead of recomputing.

Time: O(n√n) — n states, each checking up to √n squares Space: O(n) for the cache plus O(√n) recursion depth

C++

bool solve(int n, vector<int>& memo) {
    if (n == 0) return false;
    if (memo[n] != -1) return memo[n];
    for (int i = 1; i * i <= n; i++)
        if (!solve(n - i * i, memo)) return memo[n] = true;
    return memo[n] = false;
}
 
bool winnerSquareGame(int n) {
    vector<int> memo(n + 1, -1);
    return solve(n, memo);
}

Java

class Solution {
    public boolean winnerSquareGame(int n) {
        Boolean[] memo = new Boolean[n + 1];
        return solve(n, memo);
    }
    private boolean solve(int n, Boolean[] memo) {
        if (n == 0) return false;
        if (memo[n] != null) return memo[n];
        for (int i = 1; i * i <= n; i++)
            if (!solve(n - i * i, memo)) return memo[n] = true;
        return memo[n] = false;
    }
}

Python

from functools import lru_cache
 
def winner_square_game(n: int) -> bool:
    @lru_cache(maxsize=None)
    def solve(n):
        if n == 0:
            return False
        i = 1
        while i * i <= n:
            if not solve(n - i * i):
                return True
            i += 1
        return False
    return solve(n)

3. Optimal: Bottom-Up DP

Build the table from dp[0] upward instead of recursing downward. By the time you compute dp[i], every smaller state it depends on is already filled in. Same complexity class as memoization, but no call stack and better cache locality — this is what you'd actually submit.

Time: O(n√n) Space: O(n), no recursion stack

C++

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

Java

class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] dp = new boolean[n + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j * j <= i; j++)
                if (!dp[i - j * j]) { dp[i] = true; break; }
        return dp[n];
    }
}

Python

def winner_square_game(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]

The inner break matters: the moment one winning move is found for i, there's no reason to keep checking the rest of the squares.

Takeaway

The hard part of Stone Game IV was never the code, it was seeing that "does Alice win" collapses into a single per-pile-size boolean that doesn't care who's playing. Once the recurrence dp[i] = OR(!dp[i - j²]) is written down, brute force, memoization, and tabulation are just three ways of evaluating the same table.