DAY 71 - Minimum Bit Flips to Convert Number

#leetcode #coding #algorithms #beginners

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 is 1101 and goal is 1010.
The XOR of start and goal is 0111, which has three set bits.
We need to flip the bits at positions 1, 2, and 3 to transform start into goal.

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;
    }
};