Minimum Flips to Make a OR b Equal to c - Video Solutions

Problem Overview: You are given three integers a, b, and c. The goal is to flip the minimum number of bits in a or b so that the expression (a | b) == c becomes true. A flip means changing a single bit from 0 to 1 or from 1 to 0.

The key observation comes from the behavior of the bitwise OR operation. For every bit position, a | b produces 1 if at least one of the bits is 1. To make the result equal to the corresponding bit in c, you must adjust the bits in a and b accordingly.

Approach 1: Bit Manipulation by Checking Each Bit (O(32) time, O(1) space)

Iterate through each bit position from 0 to 31 and compare the bits of a, b, and c. Extract the current bit using shifts and bitwise AND: (x >> i) & 1. If the bit in c is 1, at least one of a or b must have a 1; if both are 0, one flip is required. If the bit in c is 0, both bits in a and b must be 0; each 1 contributes one flip. This approach directly simulates the OR rule for every bit and works because integers have a fixed number of bits (typically 32).

This method is straightforward and reliable. You explicitly inspect each bit and count the minimum flips needed to satisfy the condition.

Approach 2: Using Mask and Logical Reduction (O(32) time, O(1) space)

Instead of manually comparing each bit combination, compute mismatches using bitwise masks. First evaluate a | b and compare it with c. Bits where the result differs indicate positions that require flips. When c has a 1 but (a | b) has 0, exactly one flip is required to turn either bit to 1. When c has 0 but a | b has 1, you must flip every contributing 1 in a and b. Bit masks and logical operations reduce the comparisons and make the solution concise.

This approach still processes up to 32 bits but relies more heavily on bit manipulation primitives like AND, OR, and XOR. It is useful when you want compact code and leverage the properties of bitwise operations instead of explicit conditional checks.

Recommended for interviews: The per-bit iteration approach is the most common solution interviewers expect. It clearly demonstrates understanding of how the OR operation behaves at the bit level and how to extract bits using shifts. Starting with the direct bit-checking method shows solid reasoning, while recognizing mask-based optimizations shows deeper familiarity with bit manipulation patterns.