Minimum Flips to Make a OR b Equal to c — Problem & Solution
Minimum Flips to Make a OR b Equal to c solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Flips to Make a OR b Equal to c is a medium coding problem on bit manipulation, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Bit Manipulation
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given three non-negative integers a, b and c, return the minimum number of bit flips — each flip changes one bit of a or of b — needed to make (a OR b) == c.
Example 1
Input: a = 2, b = 6, c = 5
Output: 3
Example 2
Input: a = 4, b = 2, c = 7
Output: 1
Example 3
Input: a = 1, b = 2, c = 3
Output: 0
Constraints
0 <= a, b, c <= 1000000000
Hints for Minimum Flips to Make a OR b Equal to c
Hint 1
Handle each bit position on its own — flips at different positions never interact.
Hint 2
If the target bit of
cis 0, every set bit amongaandbat that position must be cleared: 0, 1 or 2 flips.Hint 3
If it is 1, you need at least one set bit there — that costs a flip only when both are 0.
How to solve Minimum Flips to Make a OR b Equal to c
Bit positions are independent: a target 0 needs every set bit among a, b cleared (0–2 flips); a target 1 needs one flip only when both are 0.
Approach
- For each bit: if
c's bit is 0, adda_bit + b_bit; else add 1 if both are 0.
Why it works
OR is computed per position, and flips at one position never affect another, so the minimum is the sum of per-position minima.
Complexity
- Time —
O(31) - Space —
O(1)
Pitfalls
- When the target is 1 and exactly one input bit is set, no flip is needed.
Reference solution
Python
def minFlips(a: int, b: int, c: int) -> int:
flips = 0
for bit in range(31):
ab = (a >> bit) & 1
bb = (b >> bit) & 1
cb = (c >> bit) & 1
if cb == 0:
flips += ab + bb
elif ab == 0 and bb == 0:
flips += 1
return flipsJava
public static int minFlips(int a, int b, int c) {
int flips = 0;
for (int bit = 0; bit < 31; bit++) {
int ab = (a >> bit) & 1;
int bb = (b >> bit) & 1;
int cb = (c >> bit) & 1;
if (cb == 0) flips += ab + bb;
else if (ab == 0 && bb == 0) flips += 1;
}
return flips;
}C++
int minFlips(int a, int b, int c) {
int flips = 0;
for (int bit = 0; bit < 31; bit++) {
int ab = (a >> bit) & 1;
int bb = (b >> bit) & 1;
int cb = (c >> bit) & 1;
if (cb == 0) flips += ab + bb;
else if (ab == 0 && bb == 0) flips += 1;
}
return flips;
}JavaScript
var minFlips = function(a, b, c) {
let flips = 0;
for (let bit = 0; bit < 31; bit++) {
const ab = (a >> bit) & 1;
const bb = (b >> bit) & 1;
const cb = (c >> bit) & 1;
if (cb === 0) flips += ab + bb;
else if (ab === 0 && bb === 0) flips += 1;
}
return flips;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 146 bit manipulation problems · the whole catalogue
Learn the technique: Bit Manipulation