TL;DR
Bits are independent, so 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 can be decided on its own and the costs added up.
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.
flowchart TD
A["bit i: ai, bi, ci"] --> B{"ci == 1?"}
B -->|no| C["cost = ai + bi"]
B -->|yes| D{"ai == 0 and bi == 0?"}
D -->|yes| E["cost = 1"]
D -->|no| F["cost = 0"]
def minFlips(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 same per-bit rules apply to all 32 positions at once with whole-word bit operations, then total with a population count instead of an 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.
def minFlips(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 or 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 apply the same rule to all bits in parallel.