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.
- Difficulty: Hard
- Topics: Dynamic Programming, Math, Game Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
A position is winning if some move leads to a losing position for the opponent.
Hint 2
The moves from
iarei - k²for everykwithk² <= i.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
- Let
win[i]say whether the player to move atistones wins;win[0] = false. - For each
ifrom 1 ton, try every squarek² <= i. - If any
win[i - k²]is false, setwin[i] = trueand stop early. - 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