Log inSign up
mediumLeetCodeNot Started

Minimum Flips to Make a OR b Equal to c

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

Given 3 positive integers a, b, and c, return the minimum number of bit flips required in a and b such that (a | b) == c.

A flip operation consists of changing any single bit 1 to 0 or changing the bit 0 to 1 in their binary representations.

Example 1 · Example 1: Mixed Flips:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: a = 0010_2, b = 0110_2, c = 0101_2. Bit 0: a=0, b=0, c=1 -> need 1 flip. Bit 1: a=1, b=1, c=0 -> need 2 flips. Bit 2: a=0, b=1, c=1 -> 0 flips. Total = 3 flips.

Example 2 · Example 2: Single Flip:

Input: a = 4, b = 2, c = 7
Output: 1
Explanation: a = 100_2, b = 010_2, c = 111_2. Only bit 0 is missing. 1 flip required.

Example 3 · Example 3: Already Equal:

Input: a = 1, b = 2, c = 3
Output: 0
Explanation: 1 | 2 = 3. No flips needed.

Constraints:

  • 1 <= a, b, c <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Derive minimal flip counts by decomposing compound bitwise expressions.
  • Convert conditional bitwise logic into branchless parallel popcount algebra.
  • Implement verified solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find minimum bit modifications across two numbers to satisfy a target bitwise OR.
  • Bit-level decision rules based on target value c.
  • Dissecting truth table entries.

Algorithmic Decision Tree:

  • Isolate excess 1s in a and b where c has 0: (a & ~c) and (b & ~c).
  • Isolate missing 1s where c has 1 but neither has 1: c & ~(a | b).

Connected Patterns:

Count Bits to Flip to Convert A to BCount Set BitsHamming Distance

1. 32-Bit Fixed Loop Inspection

Intuition

Loop i from 0 to 31. Extract ba = (a >> i) & 1, bb = (b >> i) & 1, bc = (c >> i) & 1. If bc == 0, add ba + bb. If bc == 1 and ba == 0 && bb == 0, add 1.

When to apply: Basic baseline.

Algorithm

  1. Step 1: Set flips = 0.
  2. Step 2: Loop i from 0 to 31.
  3. Step 3: Extract ba = (a >> i) & 1, bb = (b >> i) & 1, bc = (c >> i) & 1.
  4. Step 4: If bc == 0: flips += ba + bb.
  5. Step 5: Else if ba == 0 && bb == 0: flips += 1.
  6. Step 6: Return flips.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int minFlipsBrute(int a, int b, int c) {
6 int flips = 0;
7 for (int i = 0; i < 32; ++i) {
8 int ba = (a >> i) & 1;
9 int bb = (b >> i) & 1;
10 int bc = (c >> i) & 1;
11 if (bc == 0) {
12 flips += ba + bb;
13 } else {
14 if (ba == 0 && bb == 0) flips += 1;
15 }
16 }
17 return flips;
18}
19
20int main() {
21 cout << "Brute (2, 6, 5): " << minFlipsBrute(2, 6, 5) << endl; // 3
22 cout << "Brute (4, 2, 7): " << minFlipsBrute(4, 2, 7) << endl; // 1
23 return 0;
24}

Time & Space Complexity

  • Time complexity: O(32) = O(1)
  • Space complexity: O(1)

2. Dynamic Right-Shift Scan

Intuition

Loop while (a | b | c) > 0. Inspect lowest bits ba = a & 1, bb = b & 1, bc = c & 1. Update flips according to truth table, then shift all three numbers: a >>= 1, b >>= 1, c >>= 1.

When to apply: When small inputs shouldn't incur the full 32 iterations.

Algorithm

  1. Step 1: Set flips = 0.
  2. Step 2: Loop while (a | b | c) > 0.
  3. Step 3: Extract ba = a & 1, bb = b & 1, bc = c & 1.
  4. Step 4: Update flips: if bc == 0: flips += ba + bb; else if ba == 0 && bb == 0: flips += 1.
  5. Step 5: a >>= 1, b >>= 1, c >>= 1.
  6. Step 6: Return flips.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5int minFlipsShift(int a, int b, int c) {
6 int flips = 0;
7 while ((a | b | c) > 0) {
8 int ba = a & 1;
9 int bb = b & 1;
10 int bc = c & 1;
11 if (bc == 0) {
12 flips += ba + bb;
13 } else {
14 if (ba == 0 && bb == 0) flips += 1;
15 }
16 a >>= 1;
17 b >>= 1;
18 c >>= 1;
19 }
20 return flips;
21}
22
23int main() {
24 cout << "Better (2, 6, 5): " << minFlipsShift(2, 6, 5) << endl; // 3
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(log(max(a, b, c)))
  • Space complexity: O(1)

3. Parallel Popcount Expression

Intuition

Where c has bit 0, any 1 in a must be flipped (count = popcount(a & ~c)), and any 1 in b must be flipped (count = popcount(b & ~c)). Where c has bit 1, if neither a nor b has 1, we need 1 flip (count = popcount(c & ~(a | b))). The sum of these three popcounts is the exact answer in O(1) time.

When to apply: Optimal canonical solution for production and competition.

Algorithm

  1. Step 1: Compute flipsA = popcount(a & ~c).
  2. Step 2: Compute flipsB = popcount(b & ~c).
  3. Step 3: Compute flipsC = popcount(c & ~(a | b)).
  4. Step 4: Return flipsA + flipsB + flipsC.

Bit Logic Trace: a = 2 (010_2), b = 6 (110_2), c = 5 (101_2)

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Bit 0: bit_a = 0, bit_b = 0, bit_c = 1
Visual state
Values and pointers at this exact step
pointers
S
+1
0
↑ flips = 1
Check / comparison
0 | 0 != 1
Decision / next transition
Add 1 flip. Total = 1.
Why this step matters

Bit 0: bit_a = 0, bit_b = 0, bit_c = 1. Since (a | b) is 0 but c is 1, we must flip one bit to 1. flips += 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6public:
7 int minFlips(int a, int b, int c) {
8 int flipsA = __builtin_popcount(a & ~c);
9 int flipsB = __builtin_popcount(b & ~c);
10 int flipsC = __builtin_popcount(c & ~(a | b));
11 return flipsA + flipsB + flipsC;
12 }
13};
14
15int main() {
16 Solution sol;
17 cout << "Optimal (2, 6, 5): " << sol.minFlips(2, 6, 5) << endl; // 3
18 cout << "Optimal (4, 2, 7): " << sol.minFlips(4, 2, 7) << endl; // 1
19 cout << "Optimal (1, 2, 3): " << sol.minFlips(1, 2, 3) << endl; // 0
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(1)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — 32-Bit Fixed LoopO(32) = O(1)O(1)Loop through bits 0 to 31, extracting bits of a, b, and c with conditional checks.Fixed bit loop.
2.Better — Right Shift ScanO(log(max(a, b, c)))O(1)While (a | b | c) > 0, inspect lowest bits and shift all three rightward.Sequential bit shifts.
3.Optimal — Parallel Popcount ExpressionOptimalO(1)O(1)flips = popcount(a & ~c) + popcount(b & ~c) + popcount(c & ~(a | b)).Three popcount operations.

Common Pitfalls & Crucial Edge Cases

Forgetting that c_bit = 0 requires TWO flips when both a and b are 1

Flipping just one still leaves (1 | 0) = 1 != 0.

Operator precedence

Bitwise operators have lower precedence than != and ==. Always use parentheses ((a >> i) & 1).

Loop condition

Loop should continue while a > 0 || b > 0 || c > 0 or run fixed 32 iterations.

Crucial Edge Cases to Validate:

  • (a | b) == c already — Zero flips required; returns 0 immediately.
  • c = 0 — Requires flipping every set bit in both a and b to 0; result is popcount(a) + popcount(b).
  • a = 0, b = 0, c != 0 — Flips equal popcount(c).
  • Large values near 10^9 — Handled in O(32) iterations without overflow.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Formulate the decision table clearly: (1) if c_bit == 1, add 1 if both a_bit and b_bit are 0; (2) if c_bit == 0, add a_bit + b_bit.
  2. Write concise bitwise logic: flips += (a_bit + b_bit) when c_bit == 0.
  3. Mention that this runs in strict O(1) time and O(1) space.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.If the current bit of c is 0, but both a and b have bit 1 at that position, how many flips are needed?

2.If the current bit of c is 1, but neither a nor b has bit 1 at that position, how many flips are needed?

3.What is the time complexity of the bit-by-bit evaluation?

Back to DSA Sheet