Solution to LeetCode 3226 - Number of Bit Changes to Make Two Integers Equal

Problem 3226

Abstract / Summary

Count the number of differing bits between two integers to know how many changes are needed to make them equal.

Note

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

Python 3226.py

class Solution:
    def minChanges(self, n: int, k: int) -> int:
        result = 0
        while n or k:
            have = n & 1
            need = k & 1
            if have != need:
                if need:
                    return -1
                else:
                    result += 1

            n >>= 1
            k >>= 1

        return result

16 lines | 374 bytes | submitted July 26, 2024 | GitHub tab size 4 | low complexity

Difficulty

This problem is ranked as

easy medium hard

and has an acceptance rate of about 64% (80k+ submissions).

Typical patterns to solve this problem:

Bit Manipulation

I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

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.

LeetCode profile | GitHub repo

Code Walkthrough

Overview

The minChanges method determines the minimum number of bit-wise modifications required to transform the binary representation of an integer n into that of another integer k. It processes the two numbers simultaneously from the least-significant bit upward, counting mismatches that can be resolved by clearing a set bit in n. If a required bit is set in k but not present in n, the method signals impossibility by returning -1. The algorithm terminates when both numbers have been fully examined.

Key Steps

Initialization

The method starts by creating a counter result set to zero. This variable accumulates the number of bits that must be cleared in n to match k.

result = 0

Loop Over Bits

A while loop continues as long as either n or k still contains set bits. This ensures that all positions, including those beyond the most significant set bit of the smaller number, are examined.

while n or k:

Extract Current Bits

Inside the loop, the least-significant bit of each number is isolated using a bitwise AND with 1. The variables have and need represent the current bits of n and k, respectively.

have = n & 1
need = k & 1

Compare Bits and Update Counter

If the bits differ, the method distinguishes two scenarios:

When need is 1 and have is 0, the required bit cannot be created by any operation allowed in this context, so the function returns -1 immediately.
When need is 0 and have is 1, the extra set bit in n can be cleared, and the counter result is incremented.

if have != need:
    if need:
        return -1
    else:
        result += 1

Shift to Next Bit

Both numbers are right-shifted by one position to bring the next higher bit into the least-significant position. This prepares the loop for the subsequent iteration.

n >>= 1
k >>= 1

Return Result

After all bits have been processed, the accumulated count in result is returned, representing the minimal number of clear-operations needed.

return result

Edge Cases Handled

The implementation gracefully handles several boundary conditions:

Zero Inputs - When both n and k are zero, the loop body never executes and the method returns 0, indicating no changes are required.
Different Lengths - If k has more bits than n, the loop continues until k is exhausted. Encountering a 1 in k where n has already become zero triggers the early -1 return, correctly indicating impossibility.
Trailing Zeros - Bits beyond the most significant set bit of both numbers are implicitly zero; the loop terminates once both numbers are fully shifted out, avoiding unnecessary iterations.
Immediate Impossibility - The moment a required 1 in k cannot be satisfied by n, the function exits early, preventing further unnecessary computation.

Performance Optimizations

The algorithm operates directly on the binary representation without allocating auxiliary data structures, which minimizes memory overhead. Bitwise operations (&, >>) are executed in constant time on primitive integer types, making each iteration extremely fast. The early exit on an unsatisfiable bit (return -1) prevents the loop from traversing the remaining higher-order bits, saving cycles in cases where the transformation is impossible. By using a single integer counter and updating it in place, the method avoids the cost of function calls or complex state management.

Overall, the solution delivers a tight, low-level implementation that leverages the efficiency of native bitwise manipulation.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have two towers made of colorful blocks. The blocks represent numbers, and each block can either be a zero or a one. The goal is to see if you can turn the first tower into the second tower by only taking blocks away from the first one.

A little tool looks at the bottom block of each tower one by one. If the blocks are the same, that is perfect, so the tool moves on to the next pair. If the blocks are different, it checks if you can fix it. If the first tower has a zero but the second tower needs a one, that is impossible because you can only remove blocks, not add them. If that happens, the process stops. If the first tower has a one but the second tower needs a zero, you simply remove that one block from the first tower and count it as a change.

After checking each pair of blocks, the tool shuffles the towers upward to look at the next pair higher up. This continues until all the blocks have been checked. The final count of all the removed blocks is the total number of changes made.

written by google gemini

Code Quality

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

n = 27 | median = 7 | μ = 7.04 | σ = 1.88

Complexity Analysis

Time: logarithmic
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

generated automatically

	author
www	AlgoMonster		Java	C++			Python		TS
WalkCCC		Java	C++			Python
leetcode.ca		Java	C++	C#	Go	Python	Rust	TS
Progiez		Java	C++			Python
github	charles-wangkai		Java
everthis	JS
fsq			C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++

Videos

These are a few popular YouTube videos for this problem:

Developer Coder 10 mins

Number of Bit Changes to Make Two Integers Equal | Leetcode weekly-contest-407 | Java Solution

Programming Live with Larry 4 mins

3226. Number of Bit Changes to Make Two Integers Equal (Leetcode Easy)

leetcode blind 75 6 mins

leetcode 3226 : numbers of bit changes to make two integers equal: python solution

Quasar 3 mins

Leetcode 3226. Number of Bit Changes to Make Two Integers Equal | C

Coder on A Farm 6 mins

3226. Number of Bit Changes to Make Two Integers Equal (leetcode easy)

EngineerCorner 9 mins

Leetcode 3226. Number of Bit Changes to Make Two Integers Equal

ExpertFunda 11 mins