Abstract / Summary

Change elements to make the array's xor match a given value with the fewest changes.

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

Typical patterns to solve this problem:

• Array
• Bit Manipulation

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 solves the problem of determining the minimum number of bit-flip operations required to transform the cumulative XOR of an integer array nums into a target value k. It does so in a single expression that combines three built-in operations: a reduction with XOR, a final XOR with k, and a population-count of the resulting integer.

Key Steps

The core logic can be broken down into three conceptual stages, each reflected in a distinct portion of the code.

Compute the cumulative XOR of the input list

reduce(xor, nums)

The reduce function from the functools module repeatedly applies the binary xor operator (imported from operator) to the elements of nums. Starting with the first two elements, it produces an intermediate result that is XOR-ed with the next element, and so on, until a single integer representing the XOR of the entire list is obtained.

Combine the cumulative XOR with the target value

k ^ reduce(xor, nums)

The XOR operator ^ is applied between the target integer k and the cumulative XOR computed in the previous step. Because XOR is its own inverse, this operation yields a value whose set bits indicate precisely the positions where k differs from the XOR of nums.

Count the differing bits

(k ^ reduce(xor, nums)).bit_count()

The int.bit_count() method, introduced in Python 3.8, returns the number of ones in the binary representation of its operand. Applying it to the result of the previous XOR gives the exact number of bit positions that must be flipped to make the cumulative XOR equal to k. This count is the answer returned by the function.

Edge Cases Handled

The implementation gracefully accommodates several edge conditions without additional branching logic.

When k is zero, the final XOR reduces to the cumulative XOR of nums. The subsequent bit_count call then simply reports how many bits are set in that cumulative value, which corresponds to the flips needed to reach zero.

If all elements of nums are identical, their cumulative XOR may be zero (for an even count) or equal to the element value (for an odd count). The XOR with k and the population count correctly reflect the required operations in both scenarios.

The bit_count method treats negative integers by counting the ones in the absolute value’s binary representation, effectively ignoring the sign bit. Consequently, the function works for negative k or negative elements inside nums without special handling.

When nums contains a single element, reduce returns that element directly, and the remaining steps proceed unchanged. The code therefore supports the minimal non-empty input size.

Performance Optimizations

The solution leverages Python’s highly optimized C-level implementations for each operation, minimizing overhead.

The reduce function combined with the operator.xor function executes the cumulative XOR in a tight loop written in C, avoiding Python-level iteration overhead. This yields a linear-time traversal of nums with minimal per-element cost.

The final XOR and the call to bit_count are both single-instruction operations at the interpreter level. bit_count is implemented in C and uses processor-specific population-count instructions when available, delivering near-hardware speed for counting set bits.

By composing the entire algorithm into a single return statement, the code eliminates the need for temporary variables or additional data structures, reducing memory pressure and keeping the execution path short. This compact form also benefits from Python’s internal optimizations for expression evaluation.

Imagine you have a big treasure box full of colorful blocks. Each block has a secret number written on it. You want to make a special pattern with these numbers so that it matches a target number called k.

The computer does something clever here. First, it looks at every single block in the box and combines their secret numbers together. Think of it like squishing all the blocks into one giant super-block that holds the combined power of all the original numbers.

Once there is one super-block, it compares that number to the target number k. It lines them up side-by-side to see which parts are different. Every time there is a difference or a gap where the two numbers do not match, it counts that as one change that needs to happen. The final count tells you exactly how many little flips are needed to turn the combined numbers into your target number.

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		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	fsq			C++
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript

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