Minimum Flips to Make a OR b Equal to c

medium bit manipulation

Problem

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation). Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

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

Explanation

Each bit position is fully independent, because the OR of a and b at one position only depends on the bits at that same position. So we walk through all three numbers bit by bit and add up the flips needed at each spot.

We peel off the lowest bit of each with a & 1, b & 1, c & 1, then shift all three right to move to the next position. Two cases drive the cost.

If the target bit cb is 1, we need at least one of a or b to be 1. If neither is, that costs one flip; otherwise it is free. If cb is 0, then both a and b must be 0, so every 1 among them must be flipped — that adds ab + bb.

Example: a = 2 (010), b = 6 (110), c = 5 (101). Bit 0: c=1 but a=b=0 → +1. Bit 1: c=0 with a=1, b=1 → +2. Bit 2: c=1 and b=1 already → +0. Total 3.

We process one bit each loop until all numbers are exhausted, so the cost is proportional to the number of bits.

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