Vultr DocsLatest Content

Stone Game IV

Updated on 25 June, 2025
Stone Game IV header image

Problem Statement

In this strategic two-player game, Alice and Bob take turns with Alice always initiating the gameplay. There's a singular pile composed of n stones at the start. During each player's turn, the player is tasked with removing a set of stones from the pile, and the number removed must correspond to a square number (such as 1, 4, 9, etc.). A player loses if they face a scenario where no stones can be removed during their turn. The challenge here is to determine if Alice will win given a starting number n of stones if both players utilize the best strategies available.

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).

Constraints

  • 1 <= n <= 10⁵

Approach and Intuition

The game revolves around understanding the best moves at each turn when removing stones that are square numbers. Here is how you can analyze the game to determine the outcome:

  1. Base Cases:

    • If n = 1, Alice wins by removing the only stone.
    • If n = 2, Alice removes 1 stone, then Bob removes the remaining 1 stone and wins.

  2. Recursive Insight:

    • From each current n, consider all square numbers s such that s ≤ n.
    • If there's any move that leads to n - s being a losing position for the opponent, the current position is winning.
    • This mirrors the standard approach for turn-based zero-sum games where you seek to move to a state with a known loss for the opponent.

  3. Dynamic Programming:

    • Use an array dp[] where dp[i] is true if the current player can force a win with i stones.
    • Iterate i from 1 to n. For each i, try subtracting all square numbers less than or equal to i, and check if any resulting dp[i - square] is false. If so, dp[i] = true.

  4. Efficiency:

    • Since n can go up to 10⁵, the number of square numbers less than n is approximately √n.
    • Thus, this approach results in a total time complexity of roughly O(n√n), which is efficient enough under the given constraints.

By building this dynamic solution, we can accurately predict whether Alice wins with any given n using strategic foresight and mathematical properties of square numbers.

Solutions

  • Java
  • Python
java 
class Solution {
    public boolean canWin(int stones) {
        boolean[] results = new boolean[stones + 1];
        for (int index = 0; index <= stones; index++) {
            if (results[index]) {
                continue;
            }
            for (int move = 1; index + move * move <= stones; move++) {
                results[index + move * move] = true;
            }
        }
        return results[stones];
    }
}

The solution for the Stone Game IV problem is implemented in Java. It determines whether the first player can guarantee a win given a number of stones using a dynamic programming approach.

The function canWin(int stones) initializes a boolean array results where each index represents if the first player can win with that many stones left. The function iterates through each number of stones and determines if the player can force a win by making a valid square number move. If a win is possible after any such move, the corresponding index in the results array is set to true.

Understand the code flow:

  1. Initialize a boolean array results with a size of stones + 1. All values are initially set to false.
  2. Iterate over each possible stone quantity from 0 up to stones.
  3. Skip the iteration if the current index in results is already true.
  4. For valid moves, represented by square numbers (1^2, 2^2, etc.), check if the resultant index can be updated to true, indicating that a win is possible by moving to that index.
  5. Once all indices have been processed, the value at results[stones] indicates if the first player can guarantee a win starting with the original number of stones.

The approach leverages the characteristics of dynamic programming, computing solutions to subproblems and using the results to build up the solution to the main problem. The primary insight derives from ensuring that if any subsequent state (after the current index plus a square move) can force a win, the current state should mark that a win is possible.

python 
class Solution:
    def checkWin(self, stone_count: int) -> bool:
        memo = [False] * (stone_count + 1)
        for position in range(stone_count + 1):
            if memo[position]:
                continue
            for j in range(1, int(stone_count**0.5) + 1):
                if position + j * j <= stone_count:
                    memo[position + j * j] = True
                else:
                    break
        return memo[stone_count]

The provided Python solution is designed to solve a game theory problem where players alternate turns, removing a perfect square number of stones from a pile. The player who cannot make a move loses.

Here is a concise summary of how the solution works:

  • Initialize an array memo of boolean values of length equal to the number of stones plus one, filled initially with False. This array is used to store the winning state for each position.
  • Iterate over all positions from zero up to the total number of stones.
  • If the current position is already marked as a winning position in memo, skip to the next iteration.
  • For each iteration, calculate possible moves by attempting to add the square of every integer from 1 up to the square root of the total number of stones. Update the corresponding memo position if a winning position is encountered.
  • If adding a square to the current position results in a position beyond the limit of stone count, break out of the loop.
  • Finally, return the value stored for the total number of stones in the memo array, which indicates if the starting player has a guaranteed win.

This solution efficiently precomputes the winner for every possible number of stones using dynamic programming, taking advantage of the properties of perfect squares to limit the number of operations needed.

Comments

No comments yet.