Minimum Bit Flips to Convert Number solution and explanation
IBM
Google
9 more videos on this problem
L3. Minimum Bit Flips to Convert Number | Bit Manipulationtake U forward · 7:00 · 184K views
Minimum Bit Flips to Convert Number - Leetcode 2220 - PythonNeetCodeIO · 12:16 · 6K views
2220. Minimum Bit Flips to Convert Number | Bits | Leetcode Daily Challenge | DSA | Java | hindiShashCode · 8:41 · 2K views
2220. Minimum Bit Flips to Convert Number (Leetcode Easy)Programming Live with Larry · 2:10 · 403 views
LeetCode 2220 : Minimum Bit Flips to Convert Number || EASY || JAVA || Detailed SolutionCodeGPT · 8:47 · 280 views
LeetCode 2220 - Minimum Bit Flips To Convert Number - JavaAlpha-Code · 4:30 · 86 views
Minimum Bit Flips to Convert Number | Leetcode 2220 | Java Code | Developer CoderDeveloper Coder · 13:38 · 68 views
Leetcode 2220: Minimum Bit Flips to Convert Number | Leetcode Daily | C++ solutionCodefinity · 14:54 · 43 views
9/11/24: 2220. Minimum Bit Flips to Convert NumberLeetcodeDailyGrind · 5:28 · 40 views
Minimum Bit Flips to Convert Number | LeetCode 2220 Solution ExplainedAAO-CODING-KARE · 6:28 · 27 views
The problem
A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.
- For example, for
x = 7, the binary representation is111and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get110, flip the second bit from the right to get101, flip the fifth bit from the right (a leading zero) to get10111, etc.
Given two integers start and goal, return the minimum number of bit flips to convert start to goal.
Example 1:
Input: start = 10, goal = 7 Output: 3 Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps: - Flip the first bit from the right: 1010 -> 1011. - Flip the third bit from the right: 1011 -> 1111. - Flip the fourth bit from the right: 1111 -> 0111. It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.
Example 2:
Input: start = 3, goal = 4 Output: 3 Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps: - Flip the first bit from the right: 011 -> 010. - Flip the second bit from the right: 010 -> 000. - Flip the third bit from the right: 000 -> 100. It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.
Constraints:
0 <= start, goal <= 109
Note: This question is the same as 461: Hamming Distance.
Approach overview
Problem Overview: You are given two integers, start and goal. The task is to determine the minimum number of bit flips required to convert start into goal. A bit flip means changing a 0 to 1 or a 1 to 0 in the binary representation.
Approach 1: XOR and Bit Counting (Time: O(1), Space: O(1))
The key observation: a bit needs to flip only when the corresponding bits in start and goal differ. Using start ^ goal highlights exactly those positions. In XOR, matching bits produce 0 while different bits produce 1. After computing the XOR result, count how many 1 bits appear in that number. Each 1 represents a required flip. This solution relies on basic bit manipulation operations and simple bit counting. Since integers are bounded by fixed bit width (typically 32 bits), the operation runs in constant time and constant space.
Approach 2: Built-in PopCount (Time: O(1), Space: O(1))
Many languages expose optimized CPU instructions for counting set bits through functions like __builtin_popcount in C++, Integer.bitCount() in Java, or bin(x).count('1') in Python. The workflow stays the same: compute diff = start ^ goal, then call a built-in population count function to count the number of 1 bits. These functions are heavily optimized and often map directly to hardware instructions. This makes the code shorter and often slightly faster in practice while still relying on the same bit manipulation principle. The algorithmic complexity remains constant because the bit width of integers is fixed.
Recommended for interviews: The XOR + bit counting approach is the expected solution. Interviewers want to see that you recognize XOR as a tool for detecting differing bits. Writing a small loop to count set bits demonstrates understanding, while using a built-in popcount shows familiarity with language features. Both solutions operate in O(1) time and O(1) space and rely on fundamental bit manipulation concepts.
Approach 1: Using XOR and Bit Count
The simplest way to determine the different bits between two numbers is to use the XOR operation. XORing two bits will yield 1 if the bits are different and 0 if they are the same. Thus, XORing two numbers will produce a number with bits set at positions where the input numbers have different bits. Counting the number of 1s in this result will give the number of flips required.
def min_flips(start, goal):
xor = start ^ goal
count = 0
while xor:
count += xor & 1
xor >>= 1
return count
start, goal = 10, 7
print(min_flips(start, goal)) # Output: 3public class MinFlips {
public static int minFlips(int start, int goal) {
int xor = start ^ goal;
int count = 0;
while (xor != 0) {
count += xor & 1;
xor >>= 1;
}
return count;
}
public static void main(String[] args) {
int start = 10, goal = 7;
System.out.println(minFlips(start, goal)); // Output: 3
}
}#include <iostream>
int minFlips(int start, int goal) {
int xorVal = start ^ goal;
int count = 0;
while (xorVal) {
count += xorVal & 1;
xorVal >>= 1;
}
return count;
}
int main() {
int start = 10, goal = 7;
std::cout << minFlips(start, goal) << std::endl; // Output: 3
return 0;
}function minFlips(start, goal) {
let xor = start ^ goal;
let count = 0;
while (xor !== 0) {
count += xor & 1;
xor >>= 1;
}
return count;
}
let start = 10, goal = 7;
console.log(minFlips(start, goal)); // Output: 3#include <stdio.h>
int minFlips(int start, int goal) {
int xor = start ^ goal;
int count = 0;
while (xor) {
count += xor & 1;
xor >>= 1;
}
return count;
}
int main() {
int start = 10, goal = 7;
printf("%d\n", minFlips(start, goal)); // Output: 3
return 0;
}using System;
class MinFlips {
public static int MinFlipsCalc(int start, int goal) {
int xor = start ^ goal;
int count = 0;
while (xor != 0) {
count += xor & 1;
xor >>= 1;
}
return count;
}
static void Main(string[] args) {
int start = 10, goal = 7;
Console.WriteLine(MinFlipsCalc(start, goal)); // Output: 3
}
}The Python code calculates the XOR, then counts set bits (1s) in the result using bitwise manipulation.
Time Complexity: O(n) as each bit may need to be checked.
Space Complexity: O(1).
Approach 2: Using PopCount in Built-in Libraries
Many languages offer built-in functions to count the number of set bits (ones) in a binary number. Utilizing these handy functions can make our solution more concise and often more efficient. The bitwise XOR is computed between the two numbers, and the solution boils down to counting the number of set bits in the result.
def min_flips(start, goal):
return bin(start ^ goal).count('1')
start, goal = 10, 7
print(min_flips(start, goal)) # Output: 3public class MinFlips {
public static int minFlips(int start, int goal) {
return Integer.bitCount(start ^ goal);
}
public static void main(String[] args) {
int start = 10, goal = 7;
System.out.println(minFlips(start, goal)); // Output: 3
}
}#include <iostream>
#include <bit>
int minFlips(int start, int goal) {
return std::popcount(start ^ goal);
}
int main() {
int start = 10, goal = 7;
std::cout << minFlips(start, goal) << std::endl; // Output: 3
return 0;
}function minFlips(start, goal) {
return (start ^ goal).toString(2).split('1').length - 1;
}
let start = 10, goal = 7;
console.log(minFlips(start, goal)); // Output: 3#include <stdio.h>
int minFlips(int start, int goal) {
return __builtin_popcount(start ^ goal);
}
int main() {
int start = 10, goal = 7;
printf("%d\n", minFlips(start, goal)); // Output: 3
return 0;
}using System;
class MinFlips {
public static int MinFlipsCalc(int start, int goal) {
return CountBitsPopCount(start ^ goal);
}
static int CountBitsPopCount(int num) {
return Convert.ToString(num, 2).Count(c => c == '1');
}
static void Main(string[] args) {
int start = 10, goal = 7;
Console.WriteLine(MinFlipsCalc(start, goal)); // Output: 3
}
}Python makes it simple by converting the XOR result to a binary string and counting the '1's directly, a straightforward and efficient approach.
Time Complexity: O(1) because bin() and count() are optimized for small integers.
Space Complexity: O(1).
Approach 3: Bit Manipulation
According to the problem description, we only need to count the number of 1s in the binary representation of start \oplus goal.
The time complexity is O(log n), where n is the size of the integers in the problem. The space complexity is O(1).
function minBitFlips(start: number, goal: number): number {
return bitCount(start ^ goal);
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}func minBitFlips(start int, goal int) int {
return bits.OnesCount(uint(start ^ goal))
}impl Solution {
pub fn min_bit_flips(start: i32, goal: i32) -> i32 {
(start ^ goal).count_ones() as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using XOR and Bit Count | Time Complexity: O(n) as each bit may need to be checked. |
| Using PopCount in Built-in Libraries | Time Complexity: O(1) because bin() and count() are optimized for small integers. |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| XOR + Manual Bit Count | O(1) | O(1) | When demonstrating understanding of XOR and bit operations in interviews |
| XOR + Built-in PopCount | O(1) | O(1) | When the language provides optimized bit counting utilities |
Frequently asked questions
Is Minimum Bit Flips to Convert Number easy or hard?
Minimum Bit Flips to Convert Number is classified as an Easy problem. Once you recognize that XOR reveals differing bits, the solution becomes a straightforward bit counting task.
Minimum Bit Flips to Convert Number Python/Java solution
In Python, compute start ^ goal and count set bits using bin(x).count('1'). In Java, use Integer.bitCount(start ^ goal). Both implementations rely on the same XOR insight and run in constant time.
How to solve Minimum Bit Flips to Convert Number in O(1)?
Compute the XOR of start and goal to identify which bits differ. Then count the number of 1 bits in the XOR result using a loop or a built-in popcount function. Each set bit represents one flip, giving the minimum number of changes needed.
What is the best approach for Minimum Bit Flips to Convert Number?
The optimal approach uses XOR to compare the two numbers and then counts the set bits in the result. XOR highlights positions where bits differ, and counting those 1s directly gives the number of flips required. This method runs in O(1) time and O(1) space because integer bit width is fixed.
Is Minimum Bit Flips to Convert Number asked at Google/Amazon/Meta?
Bit manipulation questions like this appear frequently in technical interviews at companies such as Google, Amazon, and Meta. They test understanding of binary representation, XOR operations, and efficient bit counting techniques.
What data structure is used in Minimum Bit Flips to Convert Number?
No complex data structures are required. The solution relies purely on bit manipulation operations such as XOR and bit counting. The computation works directly on integers using binary representation.
What is the time complexity of Minimum Bit Flips to Convert Number?
The optimal solution runs in O(1) time and O(1) space. The algorithm performs a single XOR operation and counts the number of set bits in the result. Since integers have a fixed number of bits (typically 32 or 64), the work does not scale with input size.