Minimum Flips to Make a OR b Equal to c

Problem in plain words

You have three positive integers a, b and c. A flip changes one bit of a or b from 0 to 1 or from 1 to 0. Find the smallest number of flips so that a | b (bitwise OR) equals c.

For example, a = 1, b = 1, c = 0 needs 2 flips: both lowest bits are 1, and both must become 0.

Intuition

OR works on each bit position separately, so the bits never interact and each position can be fixed on its own. For one position, call the bits x (from a), y (from b) and z (from c):

• If z = 1, we need at least one of x, y to be 1. If both are 0, flip one: 1 flip. Otherwise 0.
• If z = 0, both x and y must be 0. Every 1 among them must be flipped: x + y flips (0, 1 or 2).

Summing these costs over all positions gives the answer. Extracting bits with & 1 and >> is the core trick from the bitwise operations lesson.

Approach

1. Set flips = 0.
2. While any of a, b, c is non-zero, read the lowest bits: x = a & 1, y = b & 1, z = c & 1.
3. If z == 1, add 1 when x == 0 && y == 0. If z == 0, add x + y.
4. Shift all three right by one bit and repeat.
5. Return flips.

Dry run

Input: a = 3 (0011), b = 5 (0101), c = 10 (1010).

Total: 4 flips.

Java solution

class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        while (a != 0 || b != 0 || c != 0) {
            int x = a & 1, y = b & 1, z = c & 1;
            if (z == 1) {
                if (x == 0 && y == 0) flips += 1;   // turn one bit on
            } else {
                flips += x + y;                     // turn every 1 off
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return flips;
    }
}

Python solution

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        while a or b or c:
            x, y, z = a & 1, b & 1, c & 1
            if z == 1:
                if x == 0 and y == 0:
                    flips += 1          # turn one bit on
            else:
                flips += x + y          # turn every 1 off
            a >>= 1
            b >>= 1
            c >>= 1
        return flips

Complexity

Edge cases and common mistakes

• Already equal: if a | b == c, every position costs 0 and the answer is 0.
• Counting only one flip when c's bit is 0: if both a and b have a 1 there, both must be cleared, which is 2 flips.
• Stopping when c becomes 0: higher bits of a or b may still be 1 and must be turned off. Loop until all three are 0.
• Comparing `a | b` with `c` once: Integer.bitCount((a | b) ^ c) counts mismatched positions but undercounts the case where both bits are 1 and c has 0.