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.

Description Hints 1 Solution Video 36:52

1318. Minimum Flips to Make a OR b Equal to c

Medium71.9% acceptance2 companies

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

Asked at 2 companies

Microsoft

Google

Topics

Bit Manipulation

Hints open one at a time

Hint 1

Check the bits one by one whether they need to be flipped.

36:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution