How do you solve Minimum Flips to Make a OR b Equal to c?

Iterate while any of a, b, or c has bits left. Extract the least significant bit of each. If c's bit is 0, flips equal the sum of a's and b's bits (both must be flipped to 0). If c's bit is 1, flips equal 1 only if both a's and b's bits are 0 (one flip to set either bit to 1). Right shift a, b, and c to process the next bit. Sum all flips and return the total.

Minimum Flips to Make a OR b Equal to c

Q: What is the time complexity of Minimum Flips to Make a OR b Equal to c?

O(log(max(a, b, c))). The algorithm iterates once per bit of the largest input number, which is at most 31 bits for 32-bit integers, resulting in logarithmic time complexity.

Q: What pattern does Minimum Flips to Make a OR b Equal to c use?

The Pattern: Bit Manipulation (Bitwise Iteration and Conditional Flip Counting) The Heuristic: When adjusting bits to satisfy a bitwise condition like OR, analyze each bit independently using bitwise AND and shifts, and count flips based on the minimal changes needed to achieve the target bit.

Medium Bit Manipulation

Problem

Given three integers a, b, and c, return the minimum number of bit flips required in a and b to make (a OR b) equal to c.

0 ≤ a, b, c ≤ 10⁹

Example

Input: a = 2, b = 6, c = 5

Output: 3

Representing the numbers in binary: a = 010, b = 110, c = 101. The OR of a and b is 110, which differs from c in bits 0 and 2. To fix bit 0, flip b's bit from 1 to 0 (1 flip). For bit 1, no flip needed since OR is 1 and c's bit is 0, so flip both a and b bits from 1 to 0 (2 flips). Total flips = 3. The algorithm iterates through each bit position, compares bits of a, b, and c, and counts the flips needed accordingly.

Approach

Straightforward Solution

A brute-force approach might convert a, b, and c to binary strings, pad them, and compare bit by bit, counting flips. This is inefficient and cumbersome.

Core Observation

The OR operation on bits yields 1 if either bit is 1, and 0 only if both bits are 0. To make (a OR b) equal to c at each bit, flips are needed only when the current OR bit differs from c's bit.

Path to Optimal

Preview

The key insight is to use bitwise operations to extract the least significant bit of a, b, and c in each iteration, compare them, and count flips directly without string conversion…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate while any of a, b, or c has bits left. Extract the least significant bit of each…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(log(max(a, b, c)))

The algorithm iterates once per bit of the largest input number, which is at most 31 bits for 32-bit integers, resulting in logarithmic time complexity.

Space

O(1)

Only a fixed number of integer variables are used for counting and bit extraction, with no additional data structures proportional to input size.

Pattern Spotlight

Bit Manipulation (Bitwise Iteration and Conditional Flip Counting)

When adjusting bits to satisfy a bitwise condition like OR, analyze each bit independently using bitwise AND and shifts, and count flips based on the minimal changes needed to achieve the target bit.

Solution

Python

1class Solution:
  def minFlips(self, a: int, b: int, c: int) -> int:
      flips = 0
4
      while a or b or c:
          bit_a = a & 1
          bit_b = b & 1
          bit_c = c & 1
9
          if bit_c == 0:
              flips += bit_a + bit_b
          elif bit_a == 0 and bit_b == 0:
              flips += 1
14
          a >>= 1
          b >>= 1
          c >>= 1
18
      return flips

Step-by-Step Solution

Initialize Flip Counter to Accumulate Required Bit Flips

3	`flips = 0`

Objective

To set up a counter variable that will accumulate the total number of bit flips needed.

Key Insight

A single integer variable is sufficient to track the cumulative flips as the algorithm processes each bit independently. This avoids complex data structures and keeps the solution efficient and straightforward.

Interview Quick-Check

Core Logic

Initializing a flips counter is essential to aggregate the minimal flips required across all bits.

Common Pitfalls & Bugs

Forgetting to initialize the counter or resetting it inside the loop would lead to incorrect total flips.

Iterate Through Bits of a, b, and c to Compare and Count Flips

To examine each bit of a, b, and c, determine the flips needed to make (a OR b) equal to c at that bit, and accumulate the count.

Return the Total Number of Flips After Processing All Bits

To output the accumulated count of flips required to satisfy the condition (a OR b) == c.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 10 Critical

if bit_c == 0:

Check if c's current bit is 0.

If c's bit is 0, both a's and b's bits must be flipped to 0 to satisfy (a OR b) == c at this bit.

Line 11 Critical

flips += bit_a + bit_b

Add the sum of a's and b's bits to flips when c's bit is 0.

Each bit set to 1 in a or b must be flipped to 0, so the sum of these bits equals the flips needed for this case.

Line 12 Critical

elif bit_a == 0 and bit_b == 0:

Check if c's bit is 1 and both a's and b's bits are 0.

If c's bit is 1 but both a and b have 0 bits, one flip is needed to set either a or b's bit to 1 to satisfy the OR condition.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why does the algorithm only need to examine bits until all of a, b, and c become zero?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Minimum Flips to Make a OR b Equal to c from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Flips to Make a OR b Equal to c drill

or drill a free problem

1	`class Solution:`
2	`def minFlips(self, a: int, b: int, c: int) -> int:`
3	`flips = 0`
4
5	`while a or b or c:`
6	`bit_a = a & 1`
7	`bit_b = b & 1`
8	`bit_c = c & 1`
9
10	`if bit_c == 0:`
11	`flips += bit_a + bit_b`
12	`elif bit_a == 0 and bit_b == 0:`
13	`flips += 1`
14
15	`a >>= 1`
16	`b >>= 1`
17	`c >>= 1`
18
19	`return flips`