Problem Description

Given three integers a, b, and c, all representing 32-bit non-negative integers, you need to determine the minimum number of bit flips required in a and b such that the result of a | b (the bitwise OR of a and b) equals c.

A bit flip means changing a single bit from 0 to 1 or from 1 to 0 in either a or b. You can flip any bit in a or b any number of times, and your goal is to minimize the total number of flips needed so that a | b == c.

Constraints:

• 0 ≤ a, b, c ≤ 2³¹ - 1
• There is always at least one valid solution (possibly zero flips)
• Flips can be made to any bit in a or b independently

Thought Process

The problem revolves around bit manipulation. The brute-force way would be to try all possible combinations of flips for 32 bits, but this is impractical. Instead, we observe that for each bit position, we can check the bits of a, b, and c independently.

For each bit position (from least significant to most significant), consider the following:

• What is the value of the bit in a, b, and c?
• What flips are required in a or b to make (a_bit | b_bit) == c_bit?

Solution Approach

The solution iterates through each bit position (0 to 31) and compares the bits of a, b, and c at that position. For each bit, we determine if a flip is necessary, and if so, how many flips are required.

1. For each bit position:
   • Extract the i-th bit from a, b, and c using bitwise shift and AND operations.
2. Check the desired output:
   • If c_bit is 1: At least one of a_bit or b_bit must be 1. If both are 0, we must flip one of them (cost: 1 flip).
   • If c_bit is 0: Both a_bit and b_bit must be 0. If any is 1, we must flip each 1 to 0 (cost: 1 flip for each 1).
3. Sum all the flips across all bit positions to get the minimum number of flips required.

This approach is efficient because each bit is checked independently, and there are only 32 bits to consider for 32-bit integers.

Example Walkthrough

Example: a = 2, b = 6, c = 5
Binary representations:

• a = 2 : 0b0010
• b = 6 : 0b0110
• c = 5 : 0b0101

1. Bit 0:
   • a_bit = 0, b_bit = 0, c_bit = 1
   • We need at least one 1, but both are 0. Flip one bit (cost: 1 flip)
2. Bit 1:
   • a_bit = 1, b_bit = 1, c_bit = 0
   • We need both to be 0, but both are 1. Flip both bits (cost: 2 flips)
3. Bit 2:
   • a_bit = 0, b_bit = 1, c_bit = 1
   • At least one is 1, so no flip needed. (cost: 0 flips)
4. Bit 3:
   • a_bit = 0, b_bit = 0, c_bit = 0
   • Both are already 0, so no flip needed. (cost: 0 flips)

Total flips required: 1 + 2 = 3

Time and Space Complexity

Brute-force Approach:
If we tried all possible combinations of flips for each bit, the time complexity would be exponential (O(2⁶⁴)), which is infeasible.

Optimized Approach:
Since we check each bit position independently and there are 32 bits, the time complexity is O(32) = O(1) (constant time, since 32 is fixed). The space complexity is also O(1) as we only use a few variables.

Summary

The problem of finding the minimum flips to make a | b == c is elegantly solved by analyzing each bit position independently. For each bit, we determine if a flip is required based on the values in a, b, and c. This method is highly efficient, requiring only a simple loop over the 32 bits, and avoids any unnecessary brute-force computations. The key insight is that bitwise operations allow us to decouple the problem into manageable subproblems, making the solution both intuitive and optimal.

Code Implementation

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        for i in range(32):
            a_bit = (a >> i) & 1
            b_bit = (b >> i) & 1
            c_bit = (c >> i) & 1
            if c_bit == 0:
                # Both a_bit and b_bit must be 0
                flips += a_bit + b_bit
            else:
                # At least one of a_bit or b_bit must be 1
                if a_bit == 0 and b_bit == 0:
                    flips += 1
        return flips
      

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; ++i) {
            int a_bit = (a >> i) & 1;
            int b_bit = (b >> i) & 1;
            int c_bit = (c >> i) & 1;
            if (c_bit == 0) {
                flips += a_bit + b_bit;
            } else {
                if (a_bit == 0 && b_bit == 0) {
                    flips += 1;
                }
            }
        }
        return flips;
    }
};
      

class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; i++) {
            int a_bit = (a >> i) & 1;
            int b_bit = (b >> i) & 1;
            int c_bit = (c >> i) & 1;
            if (c_bit == 0) {
                flips += a_bit + b_bit;
            } else {
                if (a_bit == 0 && b_bit == 0) {
                    flips += 1;
                }
            }
        }
        return flips;
    }
}
      

var minFlips = function(a, b, c) {
    let flips = 0;
    for (let i = 0; i < 32; i++) {
        let a_bit = (a >> i) & 1;
        let b_bit = (b >> i) & 1;
        let c_bit = (c >> i) & 1;
        if (c_bit === 0) {
            flips += a_bit + b_bit;
        } else {
            if (a_bit === 0 && b_bit === 0) {
                flips += 1;
            }
        }
    }
    return flips;
};