Hey Guys! Today we are on the 71st day and we are going to solve another bit manipulation problem.
Question: Minimum Bit Flips to Convert Number
Problem Description
Given two integers start
and goal
, both representing binary numbers, the task is to determine the minimum number of bit flips required 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.
Intuition: Bit Manipulation
- The problem can be solved using bit manipulation techniques.
- Perform a bitwise XOR operation between the start and goal integers.
- The XOR result will have 1s at the positions where the bits need to be flipped.
- To count the differing bits, repeatedly clear the rightmost 1 bit in the XOR result.
- Use the operation temp &= (temp - 1) to clear the rightmost 1 bit in the binary representation of temp.
- Each iteration of the clearing operation represents one differing bit that needs to be flipped.
- The total number of iterations directly gives the minimum number of bit flips required to convert start to goal.
Example Run
Let's take an example to understand the approach better:
- Suppose
start
is1101
andgoal
is1010
. - The XOR of
start
andgoal
is0111
, which has three set bits. - We need to flip the bits at positions 1, 2, and 3 to transform
start
intogoal
.
Code:
class Solution {
public:
int minBitFlips(int start, int goal) {
int temp = start ^ goal; // XOR to identify differing bits
int cnt = 0;
while (temp > 0) {
temp &= (temp - 1); // Clear the rightmost 1 bit
cnt++;
}
return cnt;
}
};
Complexity Analysis
Complexity | Analysis |
---|---|
Time | O(log N) |
Space | O(1) |
Top comments (2)
I see you coding and posting here daily. That's awesome keep on the Good work!!
Thanks Man! I am in my pre-final year. I wanted to stay consistent throughout the summer so started this, but now loving it!