Skip to main content
Talentd

Minimum Flips to Make a OR b Equal to c - Solution & Explanation

MediumBit Manipulation19 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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 (a OR b == 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^9
  • 1 <= b <= 10^9
  • 1 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1), consistently iterating fixed bits.
Space Complexity: O(1), as it uses primitive operations.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), as we use a constant amount of space.

Using Mask and Logical Reduction

Time Complexity: O(1), consistently iterating fixed bits.
Space Complexity: O(1), as it uses primitive operations.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit Manipulation by Checking Each BitO(32)O(1)Best for interviews and clarity. Explicitly shows how each bit contributes to the OR condition.
Using Mask and Logical ReductionO(32)O(1)Useful for concise implementations using bit masks and logical operations.

Video Solution

Minimum Flips to Make a OR b Equal to c | 2 Approaches | Microsoft | Leetcode-1318 | Explanation • codestorywithMIK • 40,443 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Flips to Make a OR b Equal to c with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Bit Flips to Convert Number