Minimum Bit Flips So a OR b Equals c

medium bit manipulation

Problem

For each bit position, compare the bits of a, b, and c. If c's bit is 0, both a and b must be 0 there (count any 1s as needing flips). If c's bit is 1, at least one of a or b must be 1 there (count one flip if both are 0). Sum the flips.

Inputa = 2 (010), b = 6 (110), c = 5 (101)

Output3

Bit 0: a=0,b=0,c=1 → +1. Bit 1: a=1,b=1,c=0 → +2. Bit 2: a=0,b=1,c=1 → 0. Total 3.

def min_flips(a, b, c):
    flips = 0
    while a or b or c:
        ab, bb, cb = a & 1, b & 1, c & 1
        if cb == 1: flips += 0 if (ab | bb) else 1
        else: flips += ab + bb
        a >>= 1; b >>= 1; c >>= 1
    return flips

function minFlips(a, b, c) {
  let flips = 0;
  while (a || b || c) {
    const ab = a & 1, bb = b & 1, cb = c & 1;
    if (cb === 1) flips += (ab | bb) ? 0 : 1;
    else flips += ab + bb;
    a >>= 1; b >>= 1; c >>= 1;
  }
  return flips;
}

class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        while ((a | b | c) != 0) {
            int ab = a & 1, bb = b & 1, cb = c & 1;
            if (cb == 1) flips += (ab | bb) != 0 ? 0 : 1;
            else flips += ab + bb;
            a >>= 1; b >>= 1; c >>= 1;
        }
        return flips;
    }
}

int minFlips(int a, int b, int c) {
    int flips = 0;
    while (a || b || c) {
        int ab = a & 1, bb = b & 1, cb = c & 1;
        if (cb == 1) flips += (ab | bb) ? 0 : 1;
        else flips += ab + bb;
        a >>= 1; b >>= 1; c >>= 1;
    }
    return flips;
}

Time: O(log max) Space: O(1)