Home | Projects | Notes > Problem Solving > LC - E - 2220. Minimum Bit Flips to Convert Number

LC - E - 2220. Minimum Bit Flips to Convert Number (bit manipulation)

Solutions in C

Solution 1

This solution uses bitwise operations.

Complexity Analysis:

• $T=O(k)$$T = O(k)$ where $k$$k$ is the number of bits set to 1 in start ^ goal

• $S=O(1)$$S = O(1)$

Solution:

xxxxxxxxxx
15
1
int minBitFlips(int start, int goal){
2
    int count = 0;
3

4
    // 1. XOR two numbers -> result will contain only the different bits set
5
    start ^= goal;
6

7
    // 2. clear least set bit one by one and count them.
8
    while (start)
9
    {
10
        start &= (start - 1); // clear the lowest set bit of 'start'
11
        count++;
12
    }
13

14
    return count;
15
}