Minimum Flips to Make a OR b Equal to c

Share

Given positive integers a, b, c: return the minimum number of bit flips in a or b to make a OR b == c.

Example 1
Input: a=2, b=6, c=5 → Output: 3
Example 2
Input: a=4, b=2, c=7 → Output: 1

Solution Approach

Check each bit position: if c-bit is 1, we need at least one of a-bit or b-bit to be 1 (cost=1 flip if both are 0). If c-bit is 0, both a-bit and b-bit must be 0 (cost = number of 1s among them).

  • Iterate over all 32 bit positions.
  • Extract bit_a = (a>>i)&1, bit_b = (b>>i)&1, bit_c = (c>>i)&1.
  • If bit_c==1 and bit_a==0 and bit_b==0: flips += 1.
  • If bit_c==0: flips += bit_a + bit_b.
Java
class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; i++) {
            int ba = (a >> i) & 1, bb = (b >> i) & 1, bc = (c >> i) & 1;
            if (bc == 1) {
                if (ba == 0 && bb == 0) flips++;
            } else {
                flips += ba + bb;
            }
        }
        return flips;
    }
}
  • Time Complexity: O(32) = O(1)
  • Space Complexity: O(1)