Skip to main content

1510. Stone Game IV

hard

Players remove a perfect-square number of stones from a single pile; whoever can't move loses. State boils down to (remaining stones) — winning iff any move leads to a losing position for the opponent.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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 in the pile. Also, if a player cannot make a move, he/she loses the game. Given a positive integer n, return true if and only if Alice wins the game, otherwise return false, assuming both players play optimally.

Constraints

  • 1 <= n <= 10^5

Examples

Example 1

Input
n = 1
Output
true

Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

Example 2

Input
n = 2
Output
false

Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).

Example 3

Input
n = 4
Output
true

Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

win[n] = true iff there exists a square k*k <= n with win[n - k*k] == false (the opponent loses).

Hint 2

Base: win[0] = false (the player to move has no stones — they lose).

Hint 3

Loop n from 1 to N and for each n try squares 1, 4, 9, ... up to n.

Hint 4

Listed in dp-2d for the game-DP family — the state is 1D but it pairs with the rest of the Stone Game series.

Solution approach

Reveal approach

Bottom-up DP. win[i] is true iff the player to move with i stones can force a win. Base case: win[0] = false. For i from 1 to n: try every perfect square k*k <= i. If win[i - k*k] is false (the opponent loses after this move), set win[i] = true and stop. Otherwise win[i] = false. Return win[n]. The dp is 1D in storage; we include it here for the Stone Game series. Time: O(n * sqrt(n)) for the inner square enumeration.

Complexity

Time
O(n * sqrt(n))
Space
O(n)

Related patterns

  • dynamic-programming
  • game-theory
  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Stone Game IV and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →