हिन्दी flagहिन्दी  
CLOSE

Suggested:

Problem Statement

Given two integers start and goal, the task is to determine the minimum number of bit flips required to convert start to goal. A bit flip means changing a bit from 0 to 1 or from 1 to 0.

Examples

Example 1:

Input: start = 10 (Binary: 1010), goal = 7 (Binary: 0111)
Output: 3

Explanation:
start = 10 in binary is 1010, and goal = 7 in binary is 0111.
        +-----+-----+-----+-----+
start = |  1  |  0  |  1  |  0  |
        +-----+-----+-----+-----+
           3     2     1     0

        +-----+-----+-----+-----+
goal  = |  0  |  1  |  1  |  1  |
        +-----+-----+-----+-----+
           3     2     1     0

We can observe that we need to flip the bits at position 0, 2 and 4 (0-based index) to convert start into goal. So ther total number of flips required is 3.
Example 2:

Input: start = 3 (Binary: 0011), goal = 4 (Binary: 0100)
Output: 3

Explanation:
start = 3 in binary is 0011, and goal = 4 in binary is 0100.
        +-----+-----+-----+-----+
start = |  0  |  0  |  1  |  1  |
        +-----+-----+-----+-----+
           3     2     1     0

        +-----+-----+-----+-----+
goal  = |  0  |  1  |  0  |  0  |
        +-----+-----+-----+-----+
           3     2     1     0

We can observe that we need to flip the bits at position 0, 1 and 2 (0-based index) to convert start into goal. So ther total number of flips required is 3.

Different Approach

1️⃣ Using Bitwise Operators

XOR Operation:

One approach to solve this problem is to use the XOR operation. XORing A and B will give result where the set bits represent the bits that need to be flipped.

Let's take the example, A = 10 and B = 15

XOR_result = 1010 ^ 1111 = 0101

Counting set bits in 0101, we get 2. So, the minimum number of bits flips is 2.

Steps:

  1. Compute start ^ goal.
  2. Count the number of set bits (number of 1s) in the result using bitwise operations.

Dry Run:

Initialization:
start = 10 (Binary: 1010)
goal = 7 (Binary: 0111)

count = 0

XOR_result = start ^ goal
           = 10 ^ 7 (in decimal)
           = 1010 ^ 0111 (in binary)
           = 1101

             +-----+-----+-----+-----+
XOR_result = |  1  |  1  |  0  |  1  |
             +-----+-----+-----+-----+
         pos    3     2     1     0
First Iteration:
count = 0
XOR_result = 1101
             +-----+-----+-----+-----+
XOR_result = |  1  |  1  |  0  |  1  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

count = count + (XOR_result & 1)
      = 0 + 1 (The rightmost bit(LSB))
      = 1
XOR_result = XOR_result >> 1
           = 0110
Second Iteration:
count = 1
XOR_result = 0110
             +-----+-----+-----+-----+
XOR_result = |  0  |  1  |  1  |  0  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

count = count + (XOR_result & 1)
      = 1 + 0 (The rightmost bit(LSB))
      = 1
XOR_result = XOR_result >> 1
           = 0011
Third iteration:
count = 1
XOR_result = 0011
             +-----+-----+-----+-----+
XOR_result = |  0  |  0  |  1  |  1  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

count = count + (XOR_result & 1)
      = 1 + 1 (The rightmost bit(LSB))
      = 2
XOR_result = XOR_result >> 1
           = 0001
Fourth Iteration:
count = 2
XOR_result = 0001
             +-----+-----+-----+-----+
XOR_result = |  0  |  0  |  0  |  1  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

count = count + (XOR_result & 1)
      = 2 + 1 (The rightmost bit(LSB))
      = 3
XOR_result = XOR_result >> 1
           = 0000
Loop Termination:
count = 3
XOR_result = 0000
             +-----+-----+-----+-----+
XOR_result = |  0  |  0  |  0  |  0  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

Since the XOR_result becomes 0, so loop will
terminated here, and return count, which have
the set bit count.

Code:

int findMinFlips(int A, int B) {
    int XOR_result = A ^ B;
    int count = 0;
    
    while (XOR_result) {
        count += XOR_result & 1;
        XOR_result >>= 1;
    }
    
    return count;
}

2️⃣ Brian Kernighan's Algorithm

Brian Kernighan's algorithm optimizes the bit-counting by continuously turning off the rightmost set bit (i.e., the 1 bit) in the XOR result until no set bits remain.

This algorithm takes advantage of the fact that for any integer x, x & (x-1) unsets the rightmost set bit. Such that we use a loop to clear the rightmost set bit in every iteration and increment the count.

XOR_result = 1010 ^ 1111 = 0101

In the first iteration, we unset the rightmost set bit making XOR_result = 0100. Count = 1.

In the second iteration, we unset the rightmost set bit, making XOR_result = 0000. Count = 2.
The minimum number of bit flips is 2.

Steps:

  1. Compute start ^ goal.
  2. Use Brian Kernighan’s algorithm to count the number of 1s.

Dry Run:

It is similar to the Approach 1 in first step, the only difference is in the counting the set bits in second step, Where the Approach 1 make use of loop, here in Brian Kernighan's Algorithm make use of formula.

Initialization:
start = 10 (Binary: 1010)
goal = 7 (Binary: 0111)

count = 0

XOR_result = start ^ goal
           = 10 ^ 7 (in decimal)
           = 1010 ^ 0111 (in binary)
           = 1101

             +-----+-----+-----+-----+
XOR_result = |  1  |  1  |  0  |  1  |
             +-----+-----+-----+-----+
         pos    3     2     1     0
First Iteration:
count = 0
XOR_result = 1101
             +-----+-----+-----+-----+
XOR_result = |  1  |  1  |  0  |  1  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

XOR_result = XOR_result & (XOR_result - 1)
           = 1101 & 1100
           = 1100
count = count + 1
      = 0 + 1
      = 1
Second Iteration:
count = 1
XOR_result = 1100
             +-----+-----+-----+-----+
XOR_result = |  1  |  1  |  0  |  0  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

XOR_result = XOR_result & (XOR_result - 1)
           = 1100 & 1011
           = 1000
count = count + 1
      = 1 + 1
      = 2
Third iteration:
count = 2
XOR_result = 1000
             +-----+-----+-----+-----+
XOR_result = |  1  |  0  |  0  |  0  |
             +-----+-----+-----+-----+
         pos    3     2     1     0

XOR_result = XOR_result & (XOR_result - 1)
           = 1000 & 0111
           = 0000
count = count + 1
      = 2 + 1
      = 3
Loop Termination:
count = 3
XOR_result = 0000
             +-----+-----+-----+-----+
XOR_result = |  0  |  0  |  0  |  0  |
             +-----+-----+-----+-----+
         pos    3     2     1     0


Since the XOR_result becomes 0, so loop will
terminated here, and return count, which have
the set bit count.

Code:

int findMinFlips(int A, int B) {
    int XOR_result = A ^ B;
    int count = 0;
    
    while (XOR_result) {
        XOR_result &= (XOR_result - 1);
        count++;
    }
    
    return count;
}

Complexity Analysis:

  • Time Complexity: O(m), where m is the number of different bits.
    • The XOR operation between two integers is performed in constant time, O(1).
    • The time complexity is O(m), where m is the number of set bits in the XOR result. This approach can be faster if the number of differing bits is small.
  • Space Complexity:O(1) – Using a couple of variables i.e., constant space.

Your experience on this site will be improved by allowing cookies Cookie Policy