Abstract / Summary

Two players take turns erasing numbers from a chalkboard and the first player can always win if the starting xor of all numbers is non zero.

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

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• 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 Solution class with a single method xorGame. The method determines whether the first player can guarantee a win in a two-player impartial game where players alternately remove numbers from a list, and the player who makes the last move loses. The logic hinges on parity of the list length and the cumulative XOR of all elements.

Key Steps

Parity Check

The first conditional evaluates the length of the input list.

if (len(nums) & 1) == 0:
    return True

The bitwise AND with 1 extracts the least-significant bit, effectively testing whether the count of numbers is even. When the count is even, the method immediately returns True, indicating that the first player has a forced win regardless of the actual values in the list.

XOR Evaluation for Odd Length

If the list length is odd, the method proceeds to compute the XOR of all elements using functools.reduce combined with the xor operator.

return reduce(xor, nums) == 0

The expression evaluates to True when the cumulative XOR equals zero, which is the condition under which the first player can still force a win despite the odd count.

Edge Cases Handled

When the input list is empty, len(nums) is 0, which satisfies the even-length condition, and the method returns True. This aligns with the game definition because there are no moves to make, and the first player trivially satisfies the win condition.

For a single-element list, the length is odd, so the XOR reduction is performed on that sole element. The result is True only when that element is 0, because 0 xor with nothing else yields 0. This correctly captures the scenario where removing the only non-zero element would cause the first player to lose, while a zero value leads to an immediate win.

If the list contains duplicate values that cancel each other out under XOR (e.g., [5, 5]), the reduction yields 0. In an odd-length context such as [5, 5, 0], the final XOR is also 0, allowing the first player to win. The code naturally accommodates these cancellations without additional logic.

Performance Optimizations

The parity test uses a bitwise operation (len(nums) & 1) instead of a modulo operation, which is marginally faster because it avoids division. This choice reduces the overhead of the initial check, especially for large inputs.

The XOR aggregation leverages functools.reduce with the built-in xor function from the operator module. This approach streams through the list in a single pass, maintaining only the running XOR value. It avoids the creation of intermediate data structures, keeping memory usage minimal and ensuring that the algorithm scales linearly with the size of the input.

By short-circuiting on the even-length case, the method bypasses the reduction entirely for half of all possible inputs, saving both time and computational effort when the list length is even. This early exit is a practical optimization that aligns with the mathematical property that an even number of elements guarantees a winning strategy for the first player.

Imagine a group of friends is playing a game with a big pile of numbered blocks. Each friend takes a turn picking up one block and putting it aside. There is a secret rule about how these blocks affect the game based on their numbers.

When there is an even number of blocks in the pile, the game starts in a way that makes it easy for the first player to win. It is like having an even number of crackers so that everyone can have a fair share.

If there is an odd number of blocks, things get trickier. The players have to look at all the numbers on the blocks and combine them in a special way. This special way is a bit like a math puzzle where the numbers cancel each other out. If the final result of this puzzle is zero, it means the players are stuck in a balanced state and the first player can win. If the result is not zero, the first player will not be able to win this specific game.

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

Time: linear
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			Java	Go
	LeetcodeHelp	C++	Python			Java
	Progiez	C++	Python			Java
github	black-shadows		Python
	charles-wangkai					Java
	everthis			JS
	fsq	C++
	halfrost						Go
	JoshCrozier			JS
	ruoru				Rust
	suxrobGM							C#
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	Python, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
ruoru	Rust
suxrobGM	C#
wisdompeak	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