Minimum Flips to Make a OR b Equal to c

Solving tips

OR is evaluated per bit, so decide each position independently and sum the costs.
Per-bit rule: if c's bit is 0, both a and b must become 0, cost = ai + bi (this is 2 when both are 1); if c's bit is 1, cost is 1 only when both a and b are 0.
Bit-parallel form: turn_on = popcount(c & ~a & ~b), plus popcount(a & ~c) and popcount(b & ~c) added separately (so the double-flip case charges 2).
Target O(1) time (32 fixed bits), O(1) space; pitfall: don't undercount the c=0-both-1 case as a single flip, and don't confuse OR with XOR.

Problem

You are given three non-negative integers a, b, and c. In one operation you may flip a single bit of a or of b (change a 0 to 1 or a 1 to 0). Return the minimum number of flips needed so that a OR b == c (bitwise OR).

Examples

a = 2, b = 6, c = 5 → 3 — a = 010, b = 110, c = 101. Bit 0: c wants 1 but both are 0 → 1 flip. Bit 1: c wants 0 but both are 1 → 2 flips. Bit 2: already fine. Total 3.
a = 4, b = 2, c = 7 → 1 — a = 100, b = 010, c = 111; only bit 0 (both 0, c wants 1) needs a flip.
a = 1, b = 2, c = 3 → 0 — 01 OR 10 = 11 = c already.

Constraints

0 <= a, b, c <= 10^9

Think about it first

Hint 1

The OR is computed independently at each bit position, so you can decide each position on its own and add up the costs.

Hint 2

If `c`'s bit is `0`, then `a`'s and `b`'s bits there must *both* be `0` — flip each one that's currently `1`. If `c`'s bit is `1`, you only need *one* of them to be `1` — so it costs a flip only when both are `0`.

Hint 3

Walk all 32 bit positions and sum those per-bit costs — or express the same rules as whole-word masks and count set bits: `c & ~a & ~b` are the bits to turn on, and `a & ~c` plus `b & ~c` are the bits to turn off.

TL;DR

Bits are independent — sum the per-position flip cost, either by looping 32 bits or by masking and popcounting — O(1) time (fixed width), O(1) space.

Approach 1 — Per-bit rules (the straightforward solution)

Because OR is evaluated bit by bit, each position is its own tiny subproblem. There is no meaningful “arithmetic brute force” here beyond enumerating bit positions and applying the rule directly.

The rule at each position i, reading ai, bi, ci:

If ci == 0: the OR must be 0, so both ai and bi must be 0. Cost = ai + bi (flip every 1 down to 0).
If ci == 1: the OR must be 1, so at least one of ai, bi must be 1. Cost = 1 only if both are currently 0, otherwise 0.

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        for i in range(32):
            ai = (a >> i) & 1
            bi = (b >> i) & 1
            ci = (c >> i) & 1
            if ci == 0:
                flips += ai + bi          # both must become 0
            elif ai == 0 and bi == 0:
                flips += 1                # need at least one 1
        return flips

Walkthrough on a = 2 (010), b = 6 (110), c = 5 (101):

bit i	ai	bi	ci	cost	reason
0	0	0	1	1	c wants 1, both 0 → 1 flip
1	1	1	0	2	c wants 0, both 1 → 2 flips
2	0	1	1	0	c wants 1, one is already 1

Sum = 3. ✓

Complexity: O(32) = O(1) time, O(1) space.

Approach 2 — Bit-parallel masks and popcount

The insight: the very same per-bit rules can be applied to all 32 positions at once with whole-word bit operations, then totalled with a population count — no explicit loop.

Bits to turn on: positions where c is 1 but neither a nor b is → c & ~a & ~b. Each costs one flip.
Bits to turn off in a: positions where c is 0 but a is 1 → a & ~c. One flip each.
Bits to turn off in b: likewise b & ~c.

The counts of a & ~c and b & ~c are added separately, which correctly charges 2 when c is 0 and both a and b are 1. ~x (bitwise NOT) selects the complementary bits; since c is a finite non-negative integer, ANDing anything with c (or with ~a/~b alongside c) yields a finite non-negative result safe to popcount.

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        turn_on = bin(c & ~a & ~b).count("1")   # c wants 1, both are 0
        off_a = bin(a & ~c).count("1")          # c wants 0, a is 1
        off_b = bin(b & ~c).count("1")          # c wants 0, b is 1
        return turn_on + off_a + off_b

Walkthrough on a = 2 (010), b = 6 (110), c = 5 (101):

c & ~a & ~b: only bit 0 has c = 1, a = 0, b = 0 → 001, popcount 1.
a & ~c: c = 0 at bit 1 where a = 1 → 010, popcount 1.
b & ~c: c = 0 at bit 1 where b = 1 → 010, popcount 1.
Total 1 + 1 + 1 = 3. ✓ (The c = 0, both-1 position correctly contributes 2, once via off_a and once via off_b.)

Complexity: O(1) time (fixed-width masks and popcount), O(1) space.

Common pitfalls

Undercounting the double flip: when c’s bit is 0 and both a and b are 1, it costs 2 flips, not 1 — the ai + bi (or the two separate popcounts) is what captures this.
Confusing OR with XOR: the target is a OR b == c, so a c-bit of 1 is satisfied by either input being 1; don’t require both.
Careless ~ in fixed-width languages: in C/Java, ~a has all high sign bits set — mask appropriately. In Python ~ is fine here because it’s always ANDed against the finite c or against finite operands.
Looping too few bits: a, b, c can reach 10^9, which needs 30 bits — loop the full 32 (or while until all three are 0).

Pattern takeaway

When an operation (OR, AND, XOR) is defined bitwise, the positions are independent: derive the cost/rule for a single bit, then either loop the fixed width or lift the rule to whole-word masks and popcount. “Decide one bit, then do all bits in parallel” is the reusable move for this whole family of problems.