Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.
Example 1:
Input: a = 2, b = 6, c = 5 Output: 3 Explanation: After flips a = 1 , b = 4 , c = 5 such that (aORb==c)
Example 2:
Input: a = 4, b = 2, c = 7 Output: 1
Example 3:
Input: a = 1, b = 2, c = 3 Output: 0
Constraints:
1 <= a <= 10^91 <= b <= 10^91 <= c <= 10^9Problem 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.
The key to this approach is analyzing each bit position of the numbers. We need to ensure that at each bit position i, (a[i] OR b[i]) matches c[i].
If c[i] is 0, both a[i] and b[i] must be 0. This may require flipping if either a[i] or b[i] is 1.
If c[i] is 1, we need at least one of a[i] or b[i] to be 1. If both are 0, we need one flip.
By iterating through each binary bit, we can count the necessary flips.
The function minFlips calculates the number of flips required to make (a OR b) equal to c. The code iterates through 32 bits (considering an integer size of 32) and uses bitwise operations to check each individual bit position of a, b, and c.
Time Complexity: O(1), since the number of bits is constant and we iterate a fixed number of times.
Space Complexity: O(1), as we use a constant amount of space.
This alternative approach uses masks and logical reduction to simplify determining the minimum flips. Instead of checking each bit individually, create a mask that highlights the bits where a OR b does not match the bits of c.
For c's zeroed bits, count additions for every 1 found in corresponding bits in a or b.
For c's one bits, ensure at least one 1 is present in the corresponding a or b position. Adjust flips accordingly.
The C function uses bitwise operations to derive a differential mask of bits that need checking. It iteratively reduces a, b, and c by shifting and adjusts flips by analyzing each bit state.
Time Complexity: O(1), consistently iterating fixed bits.
Space Complexity: O(1), as it uses primitive operations.
We can enumerate each bit of the binary representation of a, b, and c, denoted as x, y, and z respectively. If the bitwise OR operation result of x and y is different from z, we then check if both x and y are 1. If so, we need to flip twice, otherwise, we only need to flip once. We accumulate all the required flip times.
The time complexity is O(log M), where M is the maximum value of the numbers in the problem. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Bit Manipulation by Checking Each Bit | Time Complexity: O(1), since the number of bits is constant and we iterate a fixed number of times. |
| Using Mask and Logical Reduction | Time Complexity: O(1), consistently iterating fixed bits. |
| Bit Manipulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation by Checking Each Bit | O(32) | O(1) | Best for interviews and clarity. Explicitly shows how each bit contributes to the OR condition. |
| Using Mask and Logical Reduction | O(32) | O(1) | Useful for concise implementations using bit masks and logical operations. |
Minimum Flips to Make a OR b Equal to c | 2 Approaches | Microsoft | Leetcode-1318 | Explanation • codestorywithMIK • 34,997 views views
Watch 9 more video solutions →Practice Minimum Flips to Make a OR b Equal to c with our built-in code editor and test cases.
Practice on FleetCode