Abstract / Summary

Change a number to another by flipping the least number of bits in their binary representations.

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

Typical patterns to solve this problem:

• 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 defines a class Solution with a single method minBitFlips. The method receives two integer arguments, start and goal, and returns the number of bit positions that differ between them. The core logic relies on the XOR operation to highlight differing bits and then uses the built-in bit_count method to count those set bits. The solution is concise, leverages Python’s native integer handling, and directly expresses the mathematical definition of the problem.

Key Steps

The method consists of three conceptual steps, each represented by a compact line of code.

The first step computes the XOR of the two inputs, producing an integer whose binary representation contains a 1 at every position where start and goal differ.

diff = start ^ goal

The second step invokes the bit_count method on the result of the XOR. This built-in function traverses the binary representation of the integer and returns the total number of 1 bits, which corresponds exactly to the number of required flips.

flips = diff.bit_count()

The final step returns the computed count to the caller.

return flips

In the actual source the three statements are collapsed into a single expression, but the logical decomposition above clarifies the flow of data.

Edge Cases Handled

The algorithm naturally accommodates several edge conditions without additional code.

When start and goal are identical, the XOR yields zero. The binary representation of zero contains no set bits, and bit_count correctly returns 0, indicating that no flips are needed.

If either start or goal is zero, the XOR reduces to the non-zero operand. The bit_count of that operand equals the number of 1 bits in the non-zero number, which matches the flips required to transform a zero value into the target.

Both arguments can be any non-negative integer supported by Python’s arbitrary-precision integer type. The XOR operation and bit_count work uniformly across all bit widths, so values that exceed typical machine word sizes are processed correctly.

Negative inputs are not part of the problem specification, and Python’s two’s-complement representation for negative integers would produce a different set of bits. Since the method is intended for non-negative values, the existing logic aligns with the expected domain.

Performance Optimizations

The implementation benefits from several implicit optimizations provided by the Python runtime.

The XOR operator is a low-level, C-implemented operation that runs in time proportional to the number of machine words required to store the operands. Because Python integers are stored in a base-2^30 (or 2^15 on some builds) limb array, the XOR processes whole limbs at once, minimizing per-bit overhead.

The bit_count method is also a native C routine introduced in Python 3.8. It employs highly tuned algorithms, often using processor-specific instructions such as POPCNT when available, to count set bits efficiently. This avoids the need for manual loops or look-up tables in Python code.

By collapsing the XOR and counting into a single expression, the code eliminates intermediate variable allocation and reduces the number of Python-level bytecode instructions executed. The interpreter therefore spends less time on object management and more on the optimized native operations.

Overall, the solution runs with minimal overhead, leveraging the language’s built-in capabilities to achieve a fast and memory-efficient result.

Imagine two robots with flashing light patterns on their chests. A start robot and a goal robot each have a row of little lights that are either on or off, representing numbers behind the scenes. This code is like a curious detective looking at both robots at once to see which lights are different. The part with the little hat symbol compares the two patterns and marks every spot where the lights do not match. After that, the computer counts exactly how many spots are different, which tells the robots how many times they need to flip a switch to make them look exactly the same. The whole process turns the two different light patterns into one simple count of changes needed.

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

not analyzed yet

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			JS	C	Go	Rust	TS
	Progiez	C++	Python	Java
github	black-shadows	C++
	chandansgowda		Python
	charles-wangkai			Java
	DimitrisJim							C
	fartem					Ruby
	fsq	C++
	JoshCrozier						JS
	lkwq007		Python
	shreymehul				C#
	suxrobGM				C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
varunu28	Java

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