Minimum Flips to Make a OR b Equal to c

LeetCode Minimum Flips to Make a OR b Equal to c (Problem 1318) asks: given three positive integers a, b, and c, return the minimum number of bit flips in a and b to make a | b == c. A flip means changing a single bit from 0 to 1 or from 1 to 0 in the binary representation.

For example, when a = 2, b = 6, and c = 5, the answer is 3.

Why this problem matters

Bit manipulation problems show up regularly in interviews, and they tend to feel intimidating if you have not practiced the patterns. This problem is a great exercise because it forces you to think about each bit position independently. Once you internalize that habit, a whole family of bitwise problems becomes approachable.

The key insight

Check each bit position independently. At every position, extract the corresponding bit from a, b, and c, then decide how many flips that position requires:

• If c_bit is 1, you need a_bit | b_bit to be 1. If a_bit | b_bit is already 1, no flip is needed. If both are 0, flip exactly one of them. That costs 1 flip.
• If c_bit is 0, you need both a_bit and b_bit to be 0. Each one that is currently 1 must be flipped. That costs 0, 1, or 2 flips depending on how many are set.

The total across all bit positions is the answer.

The solution

def min_flips(a: int, b: int, c: int) -> int:
    flips = 0
    while a or b or c:
        a_bit = a & 1
        b_bit = b & 1
        c_bit = c & 1
        if c_bit:
            if a_bit == 0 and b_bit == 0:
                flips += 1
        else:
            flips += a_bit + b_bit
        a >>= 1
        b >>= 1
        c >>= 1
    return flips

The loop processes one bit position per iteration, starting from the least significant bit. We extract each bit with & 1, apply the rules above, then right-shift all three numbers to move to the next position. The loop ends when all three numbers have been fully consumed.

Visual walkthrough

Walking through a = 2 (010), b = 6 (110), c = 5 (101) bit by bit, we accumulate 1 + 2 + 0 = 3 flips. Bit 0 needs one flip because c wants a 1 but neither a nor b provides it. Bit 1 needs two flips because c wants a 0 but both a and b have a 1. Bit 2 needs no flip because b already provides the 1 that c needs.

Complexity analysis

The loop runs once per bit in the longest binary representation among a, b, and c. For 32-bit integers, that is at most 32 iterations. Each iteration performs a constant number of operations.

The building blocks

1. Extracting individual bits

The expression x & 1 isolates the least significant bit. Right-shifting with x >>= 1 moves the next bit into the least significant position. Together, they let you walk through every bit of a number one at a time.

while x:
    bit = x & 1
    x >>= 1

This pattern is the foundation for nearly every bit manipulation problem. You will use it for counting set bits, checking parity, and comparing binary representations.

2. Counting conditional flips

The core logic maps directly to OR truth table reasoning. When the target bit is 1, at least one input must be 1. When the target bit is 0, all inputs must be 0. Translating truth table conditions into flip counts is a reusable skill.

if c_bit:
    if a_bit == 0 and b_bit == 0:
        flips += 1
else:
    flips += a_bit + b_bit

This pattern generalizes to other bitwise target problems. Any time you need to match a desired output bit by bit, you can apply similar case analysis.

Edge cases

a | b already equals c. When no flips are needed, every bit position satisfies the condition, and the function returns 0. The loop still runs through all bits, but it never increments flips.

All bits need flipping. Consider a = 0, b = 0, c = 7 (111). Every bit of c is 1, but a | b is always 0. Each bit costs one flip, so the answer is 3.

Large values. The algorithm handles numbers up to 10^9, which fits in 30 bits. The loop runs at most 30 times, so performance is never a concern.

c is 0. When c = 0, every set bit in a and every set bit in b must be flipped to 0. The answer is the total number of set bits across a and b.

From understanding to recall

The bit-by-bit approach is simple to understand once you see it laid out. But under interview pressure, you need to recall the exact case analysis without hesitation. Which case costs 1 flip? Which costs 2? Spaced repetition locks in those details.

You practice writing the loop and the conditional logic from scratch today. A few days later, you do it again. Then a week after that. Each repetition makes the pattern faster to retrieve. When you see a bitwise problem that involves matching a target value, the per-bit analysis will come to you automatically.

Related posts

• Number of 1 Bits - Bit counting fundamentals
• Single Number - XOR bit manipulation
• Bitwise AND of Numbers Range - Range bit operations

Practice makes bit manipulation feel natural rather than intimidating.