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 Sam K., 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

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →