Min Flips OR Equal LeetCode 1318 Guide

LeetCode 1318 Minimum Flips to Make a OR b Equal to c asks you to find the minimum number of bit flips in a and b so that the bitwise OR of a and b equals c. A flip changes a single bit in either a or b from 0 to 1 or from 1 to 0. You are given three non-negative integers a, b, and c.

The naive approach would involve trying all possible combinations of flips, but that is exponential. The key insight is that bit positions in OR operations are entirely independent — what happens at bit position 0 has absolutely no effect on what happens at bit position 1. This lets us decompose the problem into 32 independent single-bit subproblems.

For each bit position, we read the bits of a, b, and c at that position and determine the minimum cost to make (a_bit OR b_bit) equal c_bit. We then sum these per-position costs for the final answer.

For each bit position i (from 0 to 31), extract the corresponding bits: a_bit = (a >> i) & 1, b_bit = (b >> i) & 1, and c_bit = (c >> i) & 1. The current OR result at this position is a_bit | b_bit. Compare it to c_bit to decide how many flips are needed.

If a_bit | b_bit already equals c_bit, no flips are needed at this position — cost is 0. If they differ, we need to flip one or more bits. The exact cost depends on whether c_bit is 0 or 1, and on the current values of a_bit and b_bit. There are only four possible (a_bit, b_bit) input combinations, making exhaustive case analysis tractable.

In practice we loop while any of a, b, or c is greater than zero, extracting the lowest bit of each with the & 1 mask and then right-shifting all three by 1 each iteration. This processes all significant bits without unnecessarily iterating over leading zeros — though capping at 32 iterations is equivalent and equally correct.

Case 1: c_bit is 1. The OR result must be 1. The OR of a_bit and b_bit is 1 whenever at least one of them is 1. If both a_bit and b_bit are already 0 (giving OR = 0), we need exactly one flip — we can flip either a_bit or b_bit to 1. If at least one is already 1 (OR = 1), cost is 0.

Case 2: c_bit is 0. The OR result must be 0. The OR of a_bit and b_bit is 0 only when both are 0. If a_bit is 1, it must flip to 0 (cost +1). If b_bit is 1, it must also flip to 0 (cost +1). The total cost at this position is a_bit + b_bit, which is 0, 1, or 2.

Together these two cases cover all possibilities. Notice that case 2 can cost 2 flips while case 1 costs at most 1 flip. The asymmetry arises because OR is a disjunctive operation: achieving a 1 requires only one cooperating bit, while achieving a 0 requires all contributing bits to be 0.

The subtle case that trips up many solvers is when c_bit is 0 but both a_bit and b_bit are 1. At first glance it may seem like one flip should suffice — after all, one flip changes the problem. But this reasoning is wrong: OR is a function of both inputs simultaneously.

When a_bit = 1 and b_bit = 1, the current OR is 1 | 1 = 1. We need OR = 0. If we flip only a_bit to 0, the OR becomes 0 | 1 = 1 — still wrong. If we flip only b_bit to 0, the OR becomes 1 | 0 = 1 — still wrong. Both bits must become 0 before the OR drops to 0. Hence the minimum cost at this position is 2.

This is fundamentally different from the c_bit = 1 case where flipping just one bit suffices because OR is satisfied by any single 1. The cost asymmetry — at most 1 for c=1, at most 2 for c=0 — is baked into the nature of the OR operation itself.

Let a = 2 (binary 010), b = 6 (binary 110), c = 5 (binary 101). We need (a OR b) = (010 OR 110) = 110 = 6 to become 101 = 5. The expected answer is 3.

Bit 0 (least significant): a_bit = 0, b_bit = 0, c_bit = 1. c=1 and OR=0 → need at least one 1 → cost 1. Bit 1: a_bit = 1, b_bit = 1, c_bit = 0. c=0 and both are 1 → must flip both → cost 2. Bit 2: a_bit = 0, b_bit = 1, c_bit = 1. c=1 and OR=1 → already correct → cost 0.

Total flips = 1 + 2 + 0 = 3. This matches the expected output. The two-flip cost at bit 1 is the critical contribution — both a and b had 1 at that position but c required 0, so both had to be cleared.

Python solution: initialize flips = 0, then loop while a or b or c. Inside the loop, extract a_bit = a & 1, b_bit = b & 1, c_bit = c & 1. If c_bit == 1 and (a_bit | b_bit) == 0, add 1 to flips. If c_bit == 0, add a_bit + b_bit to flips. Then right-shift a >>= 1, b >>= 1, c >>= 1. Return flips. Time O(32) = O(1), Space O(1).

Java solution follows identically: int flips = 0; while (a > 0 || b > 0 || c > 0) { int aBit = a & 1, bBit = b & 1, cBit = c & 1; if (cBit == 1) { if ((aBit | bBit) == 0) flips++; } else { flips += aBit + bBit; } a >>= 1; b >>= 1; c >>= 1; } return flips;

Both solutions run in constant time and constant space since integers have a fixed number of bits (32 in Java, effectively 32 for LeetCode constraints in Python). The loop executes at most 32 iterations regardless of input values. No auxiliary data structures are needed — only the three loop variables and the running flip count.

LeetCode 1318 belongs to the bitwise operation family where each bit position is processed independently. Single Number II (LeetCode 137) uses a similar per-bit-position approach but tracks counts mod 3 using a state machine. Counting Bits (LeetCode 338) and Number of 1 Bits (LeetCode 191) build the foundational skill of extracting and summing individual bit values.

Other problems in the OR/AND/XOR family include Bitwise AND of Numbers Range (LeetCode 201) and Maximum XOR of Two Numbers in an Array (LeetCode 421). Each of these requires understanding how bitwise operations compose across bit positions and what constraints at each position mean for the overall result.

To deepen bit manipulation intuition, practice expressing the four cases of (a_bit, b_bit, c_bit) combinations in a truth table. Seeing that OR requires just one 1 but zero requires both to be 0 generalizes to AND and XOR problems as well — and the per-position independence principle extends to virtually every integer bitwise problem on LeetCode.