Abstract / Summary

Players take turns removing objects from piles the player to move last loses if both play optimally the first player wins if the total number is not divisible by four

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% (900k+ submissions).

Typical patterns to solve this problem:

• 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 defines a single method, canWinNim, that determines whether the first player has a forced win in the classic Nim game when the initial pile contains n stones. The solution captures the mathematical insight that the losing positions are exactly those where the number of stones is a multiple of four. By reducing the decision to a single arithmetic test, the code delivers an immediate answer without any iterative processing.

Core Logic

The method consists of three conceptual steps, each reflected in the inline comments and the final return statement.

Step 1 - Immediate win for small piles

When the pile contains fewer than four stones, the first player can remove all stones in one move and win instantly. This situation is implicitly covered by the modulo test because any n in the range 1-3 yields a non-zero remainder when divided by four.

# 1. if less than four stones are left, you win

Step 2 - Defining the losing configuration

If exactly four stones remain, any move the first player makes leaves a pile of size 1, 2, or 3, all of which are winning positions for the opponent. Consequently, a pile of four is a losing position for the player whose turn it is.

# 2. if four stones are left, you lose

Step 3 - Generalizing the pattern

The crucial observation is that the losing condition repeats every four stones. When the total number of stones is a multiple of four, the opponent can always mirror the first player's move to maintain a multiple-of-four count after each of their turns. This mirroring strategy guarantees that the first player will eventually be forced to take the last stone.

# 3. step 2 is impossible if n is a multiple of 4 and your opponent takes 4-x stones after you took x stones

The implementation condenses these ideas into a single expression:

return n % 4 != 0

If the remainder of n divided by four is non-zero, the position is winning; otherwise, it is losing.

Edge Cases Handled

The modulo operation naturally accommodates the smallest inputs. For n = 0, the expression yields False, correctly indicating that no move is possible and the first player cannot win. For n = 1, 2, or 3, the remainder is non-zero, resulting in True, which aligns with the immediate win condition. The case n = 4 produces a zero remainder, leading to False, matching the defined losing position. All larger values follow the same periodic pattern, so the code correctly handles any non-negative integer input.

Performance Optimizations

The algorithm achieves optimal performance by avoiding loops, recursion, or auxiliary data structures. The sole operation is a single integer modulo, which executes in constant time on modern processors. Memory usage is minimal, limited to the function call stack and the integer argument, with no additional allocations. This design ensures that the method scales effortlessly to the maximum integer sizes supported by the runtime environment.

Imagine there is a big pile of shiny stones on the floor. You and a friend take turns picking up either one, two, or three stones each time. The goal is to be the person who gets to pick up the very last stone.

This little box of code is like a clever helper that looks at the pile to see if you have a winning strategy. It focuses on the number four. If there are exactly four stones, the other person will always be able to pick up whatever is left after your turn because no matter how many you take, they can finish the pile.

If the number of stones is not a perfect group of four, you can always make a move that leaves your friend with a pile that is a multiple of four. By doing this every single time, you keep your friend stuck in the losing position until the stones are all gone and you are the winner. The code performs a quick math trick by dividing the total number of stones by four to see if there is anything left over. If there is a remainder, it means you can definitely win.

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

Time: constant
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++		Python				Java
	leetcode.ca	C++		Python		Rust		Java		Go	TS
	LeetcodeHelp	C++		Python				Java
	MemoryLimitExceeded	C++		Python
	Progiez	C++		Python				Java
github	aylei					Rust
	BigEggStudy				C#
	black-shadows	C++
	chandansgowda			Python
	charles-wangkai							Java
	chenyanzhe	C++
	DimitrisJim		C
	everthis						JS
	fartem								Ruby
	haoel	C++
	JoshCrozier						JS
	keineahnung2345	C++
	Krazune		C
	lennylxx		C
	linouk23	C++
	lkwq007			Python
	muhammadfarhankt									Go
	qiyuangong			Python
	ruoru					Rust
	shreymehul				C#
	suxrobGM				C#
	varunu28							Java
	vli02		C
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
chenyanzhe	C++
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C
lennylxx	C
linouk23	C++
lkwq007	Python
muhammadfarhankt	Go
qiyuangong	Python
ruoru	Rust
shreymehul	C#
suxrobGM	C#
varunu28	Java
vli02	C
zfang399	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