Problem Statement
Given two integers start and goal, the task is to determine the minimum number of bit flips required to convert start to goal. A bit flip means changing a bit from 0 to 1 or from 1 to 0.
Examples
Example 1:
Input: start = 10 (Binary: 1010), goal = 7 (Binary: 0111)
Output: 3
Explanation:
start = 10 in binary is 1010, and goal = 7 in binary is 0111.
+-----+-----+-----+-----+
start = | 1 | 0 | 1 | 0 |
+-----+-----+-----+-----+
3 2 1 0
+-----+-----+-----+-----+
goal = | 0 | 1 | 1 | 1 |
+-----+-----+-----+-----+
3 2 1 0
We can observe that we need to flip the bits at position 0, 2 and 4 (0-based index) to convert start into goal. So the total number of flips required is 3.Example 2:
Input: start = 3 (Binary: 0011), goal = 4 (Binary: 0100)
Output: 3
Explanation:
start = 3 in binary is 0011, and goal = 4 in binary is 0100.
+-----+-----+-----+-----+
start = | 0 | 0 | 1 | 1 |
+-----+-----+-----+-----+
3 2 1 0
+-----+-----+-----+-----+
goal = | 0 | 1 | 0 | 0 |
+-----+-----+-----+-----+
3 2 1 0
We can observe that we need to flip the bits at position 0, 1 and 2 (0-based index) to convert start into goal. So ther total number of flips required is 3.Different Approach
1️⃣ Using Bitwise Operators
XOR Operation:
One approach to solve this problem is to use the XOR operation. XORing A and B will give result where the set bits represent the bits that need to be flipped.
Let's take the example, A = 10 and B = 15
XOR_result = 1010 ^ 1111 = 0101
Counting set bits in 0101, we get 2. So, the minimum number of bits flips is 2.
Steps:
- Compute
start ^ goal. - Count the number of set bits (number of
1s) in the result using bitwise operations.
Dry Run:
Initialization:
start = 10 (Binary: 1010)
goal = 7 (Binary: 0111)
count = 0
XOR_result = start ^ goal
= 10 ^ 7 (in decimal)
= 1010 ^ 0111 (in binary)
= 1101
+-----+-----+-----+-----+
XOR_result = | 1 | 1 | 0 | 1 |
+-----+-----+-----+-----+
pos 3 2 1 0First Iteration:
count = 0
XOR_result = 1101
+-----+-----+-----+-----+
XOR_result = | 1 | 1 | 0 | 1 |
+-----+-----+-----+-----+
pos 3 2 1 0
count = count + (XOR_result & 1)
= 0 + 1 (The rightmost bit(LSB))
= 1
XOR_result = XOR_result >> 1
= 0110Second Iteration:
count = 1
XOR_result = 0110
+-----+-----+-----+-----+
XOR_result = | 0 | 1 | 1 | 0 |
+-----+-----+-----+-----+
pos 3 2 1 0
count = count + (XOR_result & 1)
= 1 + 0 (The rightmost bit(LSB))
= 1
XOR_result = XOR_result >> 1
= 0011Third iteration:
count = 1
XOR_result = 0011
+-----+-----+-----+-----+
XOR_result = | 0 | 0 | 1 | 1 |
+-----+-----+-----+-----+
pos 3 2 1 0
count = count + (XOR_result & 1)
= 1 + 1 (The rightmost bit(LSB))
= 2
XOR_result = XOR_result >> 1
= 0001Fourth Iteration:
count = 2
XOR_result = 0001
+-----+-----+-----+-----+
XOR_result = | 0 | 0 | 0 | 1 |
+-----+-----+-----+-----+
pos 3 2 1 0
count = count + (XOR_result & 1)
= 2 + 1 (The rightmost bit(LSB))
= 3
XOR_result = XOR_result >> 1
= 0000Loop Termination:
count = 3
XOR_result = 0000
+-----+-----+-----+-----+
XOR_result = | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+
pos 3 2 1 0
Since the XOR_result becomes 0, so loop will
terminated here, and return count, which have
the set bit count.Code:
int findMinFlips(int A, int B) {
int XOR_result = A ^ B;
int count = 0;
while (XOR_result) {
count += XOR_result & 1;
XOR_result >>= 1;
}
return count;
}
2️⃣ Brian Kernighan's Algorithm
Brian Kernighan's algorithm optimizes the bit-counting by continuously turning off the rightmost set bit (i.e., the 1 bit) in the XOR result until no set bits remain.
This algorithm takes advantage of the fact that for any integer x, x & (x-1) unsets the rightmost set bit. Such that we use a loop to clear the rightmost set bit in every iteration and increment the count.
XOR_result = 1010 ^ 1111 = 0101
In the first iteration, we unset the rightmost set bit making XOR_result = 0100. Count = 1.
In the second iteration, we unset the rightmost set bit, making XOR_result = 0000. Count = 2.
The minimum number of bit flips is 2.
Steps:
- Compute
start ^ goal. - Use Brian Kernighan’s algorithm to count the number of
1s.
Dry Run:
It is similar to the Approach 1 in first step, the only difference is in the counting the set bits in second step, Where the Approach 1 make use of loop, here in Brian Kernighan's Algorithm make use of formula.
Initialization:
start = 10 (Binary: 1010)
goal = 7 (Binary: 0111)
count = 0
XOR_result = start ^ goal
= 10 ^ 7 (in decimal)
= 1010 ^ 0111 (in binary)
= 1101
+-----+-----+-----+-----+
XOR_result = | 1 | 1 | 0 | 1 |
+-----+-----+-----+-----+
pos 3 2 1 0First Iteration:
count = 0
XOR_result = 1101
+-----+-----+-----+-----+
XOR_result = | 1 | 1 | 0 | 1 |
+-----+-----+-----+-----+
pos 3 2 1 0
XOR_result = XOR_result & (XOR_result - 1)
= 1101 & 1100
= 1100
count = count + 1
= 0 + 1
= 1Second Iteration:
count = 1
XOR_result = 1100
+-----+-----+-----+-----+
XOR_result = | 1 | 1 | 0 | 0 |
+-----+-----+-----+-----+
pos 3 2 1 0
XOR_result = XOR_result & (XOR_result - 1)
= 1100 & 1011
= 1000
count = count + 1
= 1 + 1
= 2Third iteration:
count = 2
XOR_result = 1000
+-----+-----+-----+-----+
XOR_result = | 1 | 0 | 0 | 0 |
+-----+-----+-----+-----+
pos 3 2 1 0
XOR_result = XOR_result & (XOR_result - 1)
= 1000 & 0111
= 0000
count = count + 1
= 2 + 1
= 3Loop Termination:
count = 3
XOR_result = 0000
+-----+-----+-----+-----+
XOR_result = | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+
pos 3 2 1 0
Since the XOR_result becomes 0, so loop will
terminated here, and return count, which have
the set bit count.Code:
int findMinFlips(int A, int B) {
int XOR_result = A ^ B;
int count = 0;
while (XOR_result) {
XOR_result &= (XOR_result - 1);
count++;
}
return count;
}Complexity Analysis:
- Time Complexity:
O(m), wheremis the number of different bits.- The XOR operation between two integers is performed in constant time, O(1).
- The time complexity is O(m), where
mis the number of set bits in the XOR result. This approach can be faster if the number of differing bits is small.
- Space Complexity:
O(1)– Using a couple of variables i.e., constant space.
