#1318

Medium

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Minimum Flips to Make a OR b Equal to c

Determine the minimum number of bit flips required in two integers so that their OR equals a target integer efficiently.

bit manipulation

Problem Statement

You are given three positive integers a, b, and c. Your task is to determine the minimum number of bit flips in a and b required so that (a OR b) equals c. Each flip consists of changing a single bit from 0 to 1 or from 1 to 0 in the binary representation of a or b.

Return the minimum number of flips needed to achieve (a OR b == c). Consider each bit individually and ensure that all positions satisfy the OR operation, accounting for scenarios where both a and b might need flipping for a single bit position.

Examples

Example 1

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

Output: 3

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 details omitted.

Example 3

Input: a = 1, b = 2, c = 3

Output: 0

Example details omitted.

Constraints

1 <= a <= 10^9
1 <= b <= 10^9
1 <= c <= 10^9

Solution Approach

Iterate Through Each Bit

Check all bits from least significant to most significant. For each bit, compare the corresponding bits in a, b, and c to determine if a flip is needed. Increment a counter whenever a mismatch occurs that prevents (a OR b) from equaling c.

Handle Flip Scenarios

If a bit in c is 1 and both bits in a and b are 0, flip one of them. If a bit in c is 0 and either a or b has 1, flip all 1s to 0 in that position. This ensures the OR result matches c exactly without unnecessary flips.

Optimize Bitwise Operations

Use bit masking and shifting to isolate and evaluate each bit efficiently. This approach avoids converting to strings or arrays, reducing overhead and improving performance for large integer inputs.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) since the number of bits in the integers is bounded by 32 for standard integers, though for very large numbers it scales with the number of bits. Space complexity is O(1) because no extra data structures proportional to input size are required.

What Interviewers Usually Probe

Check bit-by-bit evaluation to see if flips are necessary.
Expect handling both zero-to-one and one-to-zero flips in a single bit position.
Optimize using bitwise masks instead of string conversion for efficiency.

Common Pitfalls or Variants

Common pitfalls

Forgetting to flip both a and b when c's bit is 0 but both a and b have 1.
Counting unnecessary flips when only one of a or b needs a change.
Iterating over a fixed number of bits without considering all significant bits of c.

Follow-up variants

Minimum flips to make a AND b equal to c, changing the bitwise operator from OR to AND.
Minimum flips to make a XOR b equal to c, focusing on XOR-specific bit conditions.
Minimum flips required when input numbers are constrained to smaller ranges or bit lengths.

FAQ

What is the main strategy for solving Minimum Flips to Make a OR b Equal to c?

The strategy involves evaluating each corresponding bit of a, b, and c, flipping bits only when necessary to satisfy the OR condition, and counting the minimal flips required.

Can I use string conversion to solve this problem?

While converting numbers to binary strings works, it is less efficient; bit masking and shifting are preferred for performance and clarity.

How do I handle a bit where both a and b have 1 but c has 0?

You must flip both bits from 1 to 0 in that position, as leaving either would prevent (a OR b) from matching c.

Is the number of flips always bounded?

Yes, the flips are bounded by the number of bits in the largest integer, since each bit can require at most two flips.

Does this problem pattern apply to AND or XOR operations?

Yes, similar bit-by-bit evaluation applies, but the flip conditions differ according to the AND or XOR logic.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        ans = 0
        for i in range(32):
            x, y, z = a >> i & 1, b >> i & 1, c >> i & 1
            ans += x + y if z == 0 else int(x == 0 and y == 0)
        return ans

Continue Practicing

#1310 xor queries of a subarray #1342 number of steps to reduce a number to zero #1349 maximum students taking exam