Minimum Bit Flips to Convert Number

Intuition

Since the problem is asking about number of bits that needs to be changed, it could be easily find out if it is known that which are bits are different.
And for this purpose, XOR operation will come in hand which will only set the bit if both corresponding bits are different.

Approach

Use the XOR operation between the two numbers. This will produce a new number where each bit is set to 1 if the corresponding bits in the original numbers were different.
Count the number of 1s in this new number because each 1 represents a bit that needs to be flipped to convert one number to the other.
Run a loop 32 times (to check all 32 bits in the number) and shift the bits of this new number one by one. Check if the least significant bit (the rightmost bit) is 1. If it is, increment the count.
Repeat this shifting process until all bits in the number have been checked. The count will give the minimum number of bit flips required to convert the first number into the second.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to get the minimum
     bit flips to convert number */
    int minBitsFlip(int start, int goal) {
        
        /* Variable to store bits that
        are different in both numbers */
        int num = start ^ goal;
        
        /* Variable to count 
        number of set bits */
        int count = 0;

        for(int i = 0; i < 32; i++) {
            /* Update count if the 
            rightmost bit is set */
            count += (num & 1); 
            
            /* Shift the number every 
            time by 1 place */
            num = num >> 1;
        }
        return count;
    }
};

int main() {
    int start = 10, goal = 7;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get the minimum
     bit flips to convert number */
    int ans = sol.minBitsFlip(start, goal);
    
    cout << "The minimum bit flips to convert number is: " << ans;
    
    return 0;
}
 class Solution {
    /* Function to get the minimum
     bit flips to convert number */
    public int minBitsFlip(int start, int goal) {
        
        /* Variable to store bits that
        are different in both numbers */
        int num = start ^ goal;
        
        /* Variable to count 
        number of set bits */
        int count = 0;

        for (int i = 0; i < 32; i++) {
            /* Update count if the 
            rightmost bit is set */
            count += (num & 1); 
            
            /* Shift the number every 
            time by 1 place */
            num = num >> 1;
        }
        return count;
    }

    public static void main(String[] args) {
        int start = 10, goal = 7;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to get the minimum
         bit flips to convert number */
        int ans = sol.minBitsFlip(start, goal);
        
        System.out.println("The minimum bit flips to convert number is: " + ans);
    }
}
class Solution:
    # Function to get the minimum 
    # bit flips to convert number
    def minBitsFlip(self, start, goal):
        
        # Variable to store bits that 
        # are different in both numbers
        num = start ^ goal
        
        # Variable to count 
        # number of set bits
        count = 0

        for i in range(32):
            # Update count if the 
            # rightmost bit is set
            count += (num & 1)
            
            # Shift the number every
            # time by 1 place
            num = num >> 1
        
        return count

# Main function
if __name__ == "__main__":
    start, goal = 10, 7
    
    # Creating an instance of Solution class
    sol = Solution()
    
    # Function call to get the minimum 
    # bit flips to convert number
    ans = sol.minBitsFlip(start, goal)
    
    print("The minimum bit flips to convert number is:", ans)
class Solution {
    /* Function to get the minimum
     bit flips to convert number */
    minBitsFlip(start, goal) {
        
        /* Variable to store bits that
        are different in both numbers */
        let num = start ^ goal;
        
        /* Variable to count 
        number of set bits */
        let count = 0;

        for (let i = 0; i < 32; i++) {
            /* Update count if the 
            rightmost bit is set */
            count += (num & 1);
            
            /* Shift the number every 
            time by 1 place */
            num = num >> 1;
        }
        return count;
    }
}

// Main function
const start = 10, goal = 7;

/* Creating an instance of 
Solution class */
const sol = new Solution();

/* Function call to get the minimum
 bit flips to convert number */
const ans = sol.minBitsFlip(start, goal);

console.log("The minimum bit flips to convert number is:", ans);

Complexity Analysis:

Time Complexity: O(1)

The XOR operation between two integers is performed in constant time, O(1).

The for loop iterates over a fixed number of bits (32 bits for a standard integer), which is as good as O(1).

Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Problem List

Minimum Bit Flips to Convert Number

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts