Stone Game IV

Hard
588.

Stone Game IV

Stone Game IV is a hard coding problem on dynamic programming, math and game theory, asked in Amazon and Google interviews.

Alice and Bob take turns with a pile of n stones, Alice first. On each turn a player must remove a non-zero square number of stones (1, 4, 9, 16, …).

A player who cannot move loses. Both play optimally. Return true if Alice wins.

Example 1

Input
n = 1
Output
true
Explanation
Alice removes the single stone.

Example 2

Input
n = 2
Output
false
Explanation
Alice must take 1, Bob takes the last one.

Example 3

Input
n = 4
Output
true
Explanation
Alice takes all four at once.

Constraints

  • 1 <= n <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var winnerSquareGame = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Stone Game IV — Solution in Python, Java & C++

Stone Game IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.

Stone Game IV is a hard coding problem on dynamic programming, math and game theory, asked in Amazon and Google interviews.

Problem statement

Alice and Bob take turns with a pile of n stones, Alice first. On each turn a player must remove a non-zero square number of stones (1, 4, 9, 16, …).

A player who cannot move loses. Both play optimally. Return true if Alice wins.

Example 1

Input: n = 1
Output: true
Explanation: Alice removes the single stone.

Example 2

Input: n = 2
Output: false
Explanation: Alice must take 1, Bob takes the last one.

Example 3

Input: n = 4
Output: true
Explanation: Alice takes all four at once.

Constraints

  • 1 <= n <= 100000

Hints for Stone Game IV

  1. Hint 1

    A position is winning if some move leads to a losing position for the opponent.

  2. Hint 2

    The moves from i are i - k² for every k with k² <= i.

  3. Hint 3

    Build the table upward from 0, which is a losing position.

How to solve Stone Game IV

Classic win/lose game DP. Position 0 is a loss for whoever must move; every other position is a win exactly when it can reach a losing one.

Approach

  1. Let win[i] say whether the player to move at i stones wins; win[0] = false.
  2. For each i from 1 to n, try every square k² <= i.
  3. If any win[i - k²] is false, set win[i] = true and stop early.
  4. Return win[n].

Why it works

Optimal play means a player wins if and only if they can hand the opponent a losing position. Since every move strictly decreases the pile, the recursion is well founded and the upward sweep computes it exactly.

Complexity

  • Time — O(n · sqrt(n))
  • Space — O(n)

Pitfalls

  • Requiring all moves to lead to a loss inverts the logic — one good move is enough.
  • There is no simple parity shortcut here; patterns like "multiples of 5 lose" break down.
  • The inner loop must include k = 1, so a single stone is always removable.

Reference solution

Python

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

Java

public static boolean winnerSquareGame(int n) {
    boolean[] win = new boolean[n + 1];
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k * k <= i; k++) {
            if (!win[i - k * k]) { win[i] = true; break; }
        }
    }
    return win[n];
}

C++

bool winnerSquareGame(int n) {
    vector<char> win(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k * k <= i; k++) {
            if (!win[i - k * k]) { win[i] = 1; break; }
        }
    }
    return win[n] != 0;
}

JavaScript

var winnerSquareGame = function(n) {
    const win = new Array(n + 1).fill(false);
    for (let i = 1; i <= n; i++) {
        for (let k = 1; k * k <= i; k++) {
            if (!win[i - k * k]) { win[i] = true; break; }
        }
    }
    return win[n];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming