Minimum bit flip to convert number

Problem Link

2220. Minimum Bit Flips to Convert Number – LeetCode

Problem Statement

Given two integers start and goal, return the minimum number of bit flips required to convert start to goal.

A bit flip changes a 0 to 1 or a 1 to 0.

Examples

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: 
Binary of 10 = 1010
Binary of 7  = 0111
Bits different at 3 positions → 3 flips required

Example 2:

Input: start = 3, goal = 4
Output: 3
Explanation:
3 = 011, 4 = 100 → All 3 bits differ

Constraints

• 0 <= start, goal <= 10⁹

Intuition

To convert start to goal, we need to find out how many bits are different between them.

This can be directly computed by:

• XOR the two numbers: start ^ goal

  • This gives a number with bits set at positions where start and goal differ

• Count the number of 1s in the result (i.e., set bits)

  • Each 1 corresponds to a bit that needs flipping

Approach: XOR + Set Bit Count (Brian Kernighan's Algorithm)

1. Perform XOR between start and goal → stores difference bits

2. Count number of 1s in XOR result using:

   • x = x & (x - 1) to remove the lowest set bit each time

3. Return the count

Java Code

class Solution {
    public int minBitFlips(int start, int goal) {
        int temp = start ^ goal;
        int cnt = 0;
        while (temp > 0) {
            temp = temp & (temp - 1); // Remove the lowest set bit
            cnt++;
        }
        return cnt;
    }
}

Time and Space Complexity

Dry Run

Input: start = 10, goal = 7

• Binary:

  • 10 = 1010

  • 7 = 0111

• XOR: 1010 ^ 0111 = 1101 → 3 set bits → 3 flips

Conclusion

This problem is a direct application of bitwise XOR and set bit counting.

It highlights key concepts:

• XOR to find difference

• Efficient bit counting via Brian Kernighan’s method (x = x & (x - 1))

It's an excellent example of applying bit manipulation to solve real problems with constant space and logarithmic time.