Minimum Bit Flips to Convert Number — Problem & Solution
Minimum Bit Flips to Convert Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Bit Flips to Convert Number is an easy coding problem on bit manipulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Bit Manipulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A bit flip changes a single bit of a number's binary representation from 0 to 1 or from 1 to 0.
Given two non-negative integers start and goal, return the minimum number of bit flips that turn start into goal.
Example 1
Input: start = 10, goal = 7
Output: 3
Example 2
Input: start = 3, goal = 4
Output: 3
Example 3
Input: start = 8, goal = 8
Output: 0
Constraints
0 <= start, goal <= 1000000000
Hints for Minimum Bit Flips to Convert Number
Hint 1
Each differing bit needs exactly one flip, and identical bits need none.
Hint 2
start ^ goalmarks precisely the differing positions.Hint 3
So the answer is the popcount of that XOR.
How to solve Minimum Bit Flips to Convert Number
Each differing bit needs exactly one flip: popcount of start ^ goal.
Approach
- Return the number of set bits in
start ^ goal.
Why it works
The XOR is 1 precisely at the positions that must change.
Complexity
- Time —
O(1) - Space —
O(1)
Pitfalls
- Identical to Hamming distance.
Reference solution
Python
def minBitFlips(start: int, goal: int) -> int:
return bin(start ^ goal).count("1")Java
public static int minBitFlips(int start, int goal) {
int v = start ^ goal;
int count = 0;
while (v != 0) {
v &= v - 1;
count++;
}
return count;
}C++
int minBitFlips(int start, int goal) {
unsigned int v = (unsigned int) (start ^ goal);
int count = 0;
while (v) {
v &= v - 1;
count++;
}
return count;
}JavaScript
var minBitFlips = function(start, goal) {
let v = (start ^ goal) >>> 0;
let count = 0;
while (v > 0) {
v &= v - 1;
count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 146 bit manipulation problems · the whole catalogue
Learn the technique: Bit Manipulation