Stone Game IV - Practice Coding Problems

Stone Game IV - 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.

Input & Output

Example 1 — Alice Wins

$ Input: n = 1

› Output: true

💡 Note: Alice can remove 1² = 1 stone, leaving 0 stones for Bob. Bob cannot make a move and loses.

Example 2 — Alice Loses

$ Input: n = 2

› Output: true

💡 Note: Alice can remove 1² = 1 stone, leaving 1 stone for Bob. Bob removes 1 stone and Alice loses.

Example 3 — Complex Case

$ Input: n = 4

› Output: true

💡 Note: Alice can remove 4 stones (2²=4), leaving 0 for Bob. Or remove 1 stone leaving 3 for Bob. Alice has winning moves.

Constraints

1 ≤ n ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Game Rules

Players alternate removing square numbers of stones (1, 4, 9, 16...)

Winning Strategy

Position is winning if any move leads to losing position for opponent

DP Solution

Build table of winning/losing positions from bottom up

Key Takeaway

🎯 Key Insight: A position is winning if you can make a move that puts your opponent in a losing position

Asked in

G Google 15 F Facebook 12 a Amazon 8

The key insight is that this is a classic game theory problem solvable with dynamic programming. A position is winning if there exists at least one move that leads to a losing position for the opponent. Best approach is bottom-up DP building from base cases. Time: O(n√n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(n^(3/2))	O(√n)	Try all possible square moves recursively to determine winner
Dynamic Programming (Bottom-up)	O(n√n)	O(n)	Build solution from base cases upward using DP array
Memoized Recursion	O(n√n)	O(n)	Cache recursive results to avoid recalculating same positions

Recursive Brute Force — Algorithm Steps

For current position n, try removing 1², 2², 3²... stones
Recursively check if opponent loses from remaining position
If any move makes opponent lose, current player wins

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Start with n stones, Alice's turn

Try Moves

Try removing 1², 2², 3²... stones recursively

Check Result

If any move leads to Bob losing, Alice wins

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

bool canWin(int stones) {
    if (stones == 0) {
        return false;
    }
    
    for (int i = 1; i * i <= stones; i++) {
        if (!canWin(stones - i * i)) {
            return true;
        }
    }
    return false;
}

bool solution(int n) {
    return canWin(n);
}

int main() {
    int n;
    scanf("%d", &n);
    bool result = solution(n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^(3/2))

For each position, try √n possible moves, with exponential branching

✓ Linear Growth

Space Complexity

O(√n)

Recursion depth limited by largest square ≤ n

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler