Abstract / Summary

Players take turns splitting a stone pile into smaller parts to maximize their score difference against the opponent.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (100k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Game Theory
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether the first player can force a win in the classic “Stone Game” where each move consists of removing a perfect-square number of stones. The algorithm builds a collection of square numbers up to the target, then explores the game tree recursively while memoizing results to avoid repeated work. Early termination conditions and a pre-computed set of squares give the solution a practical runtime even for larger inputs.

Key Steps

Building the set of square numbers

squares = set()
for i in range(1, floor(n**0.5)):
    squares.add(i*i)

All perfect squares less than n are stored in a hash-based container. The constant-time membership test that follows relies on this set.

Recursive evaluation with memoization

@cache
def deeper(stones):
    if stones == 0:
        return False

    if stones in squares:
        return True

    i = floor(sqrt(n))          # pick as many as possible
    while i > 0:
        if stones - i*i >= 0 and not deeper(stones - i*i):
            return True
        i -= 1

    return False

The inner function deeper returns True when the current player has a winning strategy from the given stone count. The @cache decorator automatically stores each distinct argument, turning the exponential recursion into a polynomial-time process.

Initiating the computation

return deeper(n)

The public method simply forwards the original pile size to the memoized helper.

Edge Cases Handled

When the pile is empty (stones == 0), the function returns False, correctly indicating that the player whose turn it is cannot move and therefore loses.

If the current pile size itself is a perfect square (stones in squares), the function returns True immediately, reflecting the fact that the player can remove all stones in one move and win.

The loop guard stones - i*i >= 0 prevents attempts to subtract a square larger than the remaining stones, ensuring the recursion never receives a negative argument.

The range used to generate squares stops before floor(n**0.5), which means the largest square considered is strictly less than n. The later check stones in squares still works for any intermediate value because the set contains all squares up to the maximum possible intermediate pile size (which can never exceed the original n).

Performance Optimizations

The use of a set for square numbers provides O(1) average lookup when testing stones in squares.

Memoization via @cache eliminates duplicate sub-problem evaluations. Once the outcome for a particular stone count is known, subsequent calls retrieve the stored result instantly, turning what would be an exponential search into a dynamic-programming style solution.

The loop starts from floor(sqrt(n)) and decrements, attempting the largest feasible square first. This heuristic often discovers a winning move early, allowing the function to return without exploring smaller squares.

The early return on perfect-square piles (if stones in squares: return True) cuts off the recursion at the deepest possible level for those states, avoiding unnecessary deeper calls.

Collectively, these choices keep the algorithm efficient for the problem constraints while preserving a clear, recursive structure.

Imagine a game played with a pile of rocks. The number of rocks is named n. To play, you must take away a square number of rocks, like one, four, nine, or sixteen. Two people take turns doing this until the pile is empty. The person who takes the last rock wins because there are none left for the next person.

The code is like a clever helper that looks ahead to see who will win. It starts by making a collection of all the possible square numbers that are not bigger than the pile. Then, it creates a way to think through every possible move. It tests taking away each square number one by one. If it finds even one move that leaves the other person stuck with no moves left to win, then the current person knows they can win. It keeps checking these possibilities by acting out the game over and over again until it understands the outcome. Even though it acts like it is playing many games, it remembers what it learned so it does not have to do the same work twice.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java			TS
	WalkCCC	C++			Java
	leetcode.ca	C++	Python		Java		Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	FelixFan1122					C#
	fsq	C++
	gouthampradhan				Java
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	MacJim	C++
	muhammadfarhankt						Go
	suxrobGM					C#
	trung-hn		Python
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	C#
fsq	C++
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
MacJim	C++
muhammadfarhankt	Go
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality