Minimum Flips to Make a OR b Equal to c solution and explanation
Google
9 more videos on this problem
Minimum Flips to Make a OR b Equal to c | 2 Approaches | Microsoft | Leetcode-1318 | ExplanationcodestorywithMIK · 36:52 · 40K views
Minimum Flips to Make a OR b Equal to c II Bit Manipulation || And, Or, Xor || Leetcode 1318Aryan Mittal · 18:55 · 4K views
Minimum Flips to Make a OR b Equal to c - Leetcode 1318 - PythonTechError · 5:37 · 2K views
1318. Minimum Flips to Make a OR b Equal to c || leetcode || medium problem || c++code Explainer · 4:53 · 1K views
Minimum Flips to Make a OR b Equal to c #leetcode #leetcode75Deepti Talesra · 7:47 · 1K views
1318. Minimum Flips to Make a OR b Equal to cTech Adora by Nivedita · 10:30 · 928 views
Minimum Flips to Make a OR b Equal to c (Leetcode 1318)Coding Interviews · 11:37 · 840 views
Leetcode 1318: Minimum Flips to Make a OR b Equal to cAlgorithms Casts · 17:38 · 690 views
Daily Leetcode #1163: Jun 07, 2023 - 1318. Minimum Flips to Make a OR b Equal to cProgramming Live with Larry · 8:52 · 507 views
Leetcode 1318. Minimum Flips to Make a OR b Equal to cElite Code · 12:03 · 499 views
The problem
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^9
Approach overview
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.
Approach 1: Bit Manipulation by Checking Each Bit
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.
def minFlips(a: int, b: int, c: int) -> int:
flips = 0
for i in range(32):
bitA = (a >> i) & 1
bitB = (b >> i) & 1
bitC = (c >> i) & 1
if bitC == 0:
flips += bitA + bitB
else:
if bitA == 0 and bitB == 0:
flips += 1
return flips
print(minFlips(2, 6, 5))public class MinFlips {
public int minFlips(int a, int b, int c) {
int flips = 0;
for (int i = 0; i < 32; i++) {
boolean bitA = (a & (1 << i)) != 0;
boolean bitB = (b & (1 << i)) != 0;
boolean bitC = (c & (1 << i)) != 0;
if (!bitC) {
flips += (bitA ? 1 : 0) + (bitB ? 1 : 0);
} else {
flips += (!bitA && !bitB) ? 1 : 0;
}
}
return flips;
}
public static void main(String[] args) {
MinFlips instance = new MinFlips();
int result = instance.minFlips(2, 6, 5);
System.out.println(result);
}
}#include <iostream>
using namespace std;
int minFlips(int a, int b, int c) {
int flips = 0;
for(int i = 0; i < 32; ++i) {
int bitA = (a >> i) & 1;
int bitB = (b >> i) & 1;
int bitC = (c >> i) & 1;
if (bitC == 0) {
flips += bitA + bitB;
} else {
flips += !(bitA | bitB);
}
}
return flips;
}
int main() {
int a = 2, b = 6, c = 5;
cout << minFlips(a, b, c) << endl;
return 0;
}function minFlips(a, b, c) {
let flips = 0;
for (let i = 0; i < 32; i++) {
let bitA = (a >> i) & 1;
let bitB = (b >> i) & 1;
let bitC = (c >> i) & 1;
if (bitC === 0) {
flips += bitA + bitB;
} else {
flips += ((bitA | bitB) === 0) ? 1 : 0;
}
}
return flips;
}
console.log(minFlips(2, 6, 5));#include <stdio.h>
int minFlips(int a, int b, int c) {
int flips = 0;
for(int i = 0; i < 32; ++i) {
int bitA = (a >> i) & 1;
int bitB = (b >> i) & 1;
int bitC = (c >> i) & 1;
if (bitC == 0) {
flips += bitA + bitB;
} else {
flips += !(bitA | bitB);
}
}
return flips;
}
int main() {
int a = 2, b = 6, c = 5;
printf("%d\n", minFlips(a, b, c));
return 0;
}using System;
public class MinFlipsSolution {
public int MinFlips(int a, int b, int c) {
int flips = 0;
for (int i = 0; i < 32; i++) {
int bitA = (a >> i) & 1;
int bitB = (b >> i) & 1;
int bitC = (c >> i) & 1;
if (bitC == 0) {
flips += bitA + bitB;
} else {
if ((bitA | bitB) == 0)
flips += 1;
}
}
return flips;
}
public static void Main() {
MinFlipsSolution solution = new MinFlipsSolution();
Console.WriteLine(solution.MinFlips(2, 6, 5));
}
}In Python, the function iterates through the 32 possible bit positions and evaluates the states of bits from a, b, and c. It accumulates the count of flips needed where (a OR b) does not match c.
Time Complexity: O(1) due to a constant number of operations.
Space Complexity: O(1).
Approach 2: Using Mask and Logical Reduction
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.
def minFlips(a: int, b: int, c: int) -> int:
flips = 0
while a or b or c:
if (c & 1) == 0:
flips += (a & 1) + (b & 1)
elif (a & 1) == 0 and (b & 1) == 0:
flips += 1
a >>= 1
b >>= 1
c >>= 1
return flips
print(minFlips(2, 6, 5))public class MinFlipsAlternate {
public int minFlips(int a, int b, int c) {
int flips = 0;
while (c > 0 || a > 0 || b > 0) {
int bitA = a & 1;
int bitB = b & 1;
int bitC = c & 1;
if (bitC == 0) {
flips += (bitA + bitB);
} else if (bitA == 0 && bitB == 0) {
flips++;
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return flips;
}
public static void main(String[] args) {
MinFlipsAlternate solution = new MinFlipsAlternate();
System.out.println(solution.minFlips(2, 6, 5));
}
}#include <iostream>
using namespace std;
int minFlips(int a, int b, int c) {
int flips = 0;
while (c > 0 || a > 0 || b > 0) {
if ((c & 1) == 0) {
flips += (a & 1) + (b & 1);
} else if ((a & 1) == 0 && (b & 1) == 0) {
flips++;
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return flips;
}
int main() {
cout << minFlips(2, 6, 5) << endl;
return 0;
}function minFlips(a, b, c) {
let flips = 0;
while (a > 0 || b > 0 || c > 0) {
let bitA = a & 1;
let bitB = b & 1;
let bitC = c & 1;
if (bitC === 0) {
flips += bitA + bitB;
} else if ((bitA | bitB) === 0) {
flips++;
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return flips;
}
console.log(minFlips(2, 6, 5));#include <stdio.h>
int minFlips(int a, int b, int c) {
int flips = 0;
int diff = a | b;
while(c > 0 || diff > 0) {
int bitA = a & 1;
int bitB = b & 1;
int bitC = c & 1;
if (bitC == 0) {
flips += (bitA + bitB);
} else if ((bitA | bitB) == 0) {
flips++;
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return flips;
}
int main() {
printf("%d\n", minFlips(2, 6, 5));
return 0;
}using System;
public class MinFlipsAlternative {
public int MinFlips(int a, int b, int c) {
int flips = 0;
while (a > 0 || b > 0 || c > 0) {
int bitA = a & 1;
int bitB = b & 1;
int bitC = c & 1;
if (bitC == 0) {
flips += (bitA + bitB);
} else if (bitA == 0 && bitB == 0) {
flips++;
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return flips;
}
public static void Main() {
MinFlipsAlternative solution = new MinFlipsAlternative();
Console.WriteLine(solution.MinFlips(2, 6, 5));
}
}The Python version simplifies using while-loops ensuring active bits in any of the variables. Flips are incrementally accumulated through logical deductions.
Time Complexity: O(1). Uniform bit size checks guarantee consistent performance.
Space Complexity: O(1).
Approach 3: Bit Manipulation
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).
function minFlips(a: number, b: number, c: number): number {
let ans = 0;
for (let i = 0; i < 32; ++i) {
const [x, y, z] = [(a >> i) & 1, (b >> i) & 1, (c >> i) & 1];
ans += z === 0 ? x + y : x + y === 0 ? 1 : 0;
}
return ans;
}func minFlips(a int, b int, c int) (ans int) {
for i := 0; i < 32; i++ {
x, y, z := a>>i&1, b>>i&1, c>>i&1
if z == 0 {
ans += x + y
} else if x == 0 && y == 0 {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation by Checking Each Bit | Time Complexity: O(1) due to a constant number of operations. |
| Using Mask and Logical Reduction | Time Complexity: O(1). Uniform bit size checks guarantee consistent performance. |
| Bit Manipulation | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Flips to Make a OR b Equal to c easy or hard?
The problem is classified as Medium because it requires understanding how bitwise OR behaves at the binary level. Once the bit rules are recognized, the implementation becomes straightforward with a constant-time bit iteration.
Minimum Flips to Make a OR b Equal to c Python/Java solution
Most implementations loop through 32 bit positions and use expressions like (a >> i) & 1 to read bits. The logic counts flips based on the relationship between a, b, and c at each position. The same approach works consistently across Python, Java, C++, and JavaScript.
How to solve Minimum Flips to Make a OR b Equal to c in O(n)?
Treat each bit independently. Extract the i-th bit of a, b, and c using bit shifts and AND operations. If c has 1 and both a and b have 0, one flip is required. If c has 0, every 1 in a or b at that position must be flipped, contributing one flip each.
What is the best approach for Minimum Flips to Make a OR b Equal to c?
The most common solution checks each bit of a, b, and c individually using bit manipulation. For every bit position, apply the rules of the OR operation and count how many flips are needed to match c. This approach runs in O(32) time and O(1) space since integers have a fixed number of bits.
Is Minimum Flips to Make a OR b Equal to c asked at Google/Amazon/Meta?
Bit manipulation problems similar to this appear in interviews at companies like Amazon, Google, and Meta. Questions often test understanding of bitwise operators, masks, and reasoning about binary representations.
What data structure is used in Minimum Flips to Make a OR b Equal to c?
No special data structure is required. The solution relies purely on bit manipulation techniques such as bit shifting, AND, OR, and XOR operations while iterating through the bits of the integers.
What is the time complexity of Minimum Flips to Make a OR b Equal to c?
The time complexity is O(32), which is effectively O(1). The algorithm iterates through each bit position of the integers (usually 32 bits) and performs constant-time bitwise operations at every step.