LeetCode 1318 - Minimum Flips to Make a OR b Equal to c

The problem gives us three positive integers, a, b, and c. We are allowed to flip individual bits in either a or b. A flip means changing a bit from 0 to 1 or from 1 to 0. Our goal is to perform the minimum number of bit flips so that: The OR operation works bit by bit.

leetcodemediumbit-manipulation

LeetCode Problem 1318

Difficulty: 🟡 Medium
Topics: Bit Manipulation

Solution

Problem Understanding

The problem gives us three positive integers, a, b, and c. We are allowed to flip individual bits in either a or b. A flip means changing a bit from 0 to 1 or from 1 to 0.

Our goal is to perform the minimum number of bit flips so that:

(a OR b) == c

The OR operation works bit by bit. For each bit position:

  • 0 OR 0 = 0
  • 0 OR 1 = 1
  • 1 OR 0 = 1
  • 1 OR 1 = 1

This means that for every bit position, the resulting bit in (a OR b) must exactly match the corresponding bit in c.

The important observation is that each bit position is completely independent from the others. A decision made for one bit does not affect any other bit. Because of this, we can process the integers one bit at a time.

The constraints are:

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

Since 10^9 fits within 30 bits, we only need to examine around 30 to 31 bit positions. This immediately suggests that a bit manipulation solution will be extremely efficient.

There are several important edge cases to consider:

  • When (a OR b) already equals c, the answer should be 0.
  • When a bit in c is 0, both corresponding bits in a and b must become 0. If both are currently 1, we need two flips.
  • When a bit in c is 1, at least one of the corresponding bits in a or b must be 1. If both are currently 0, we need one flip.
  • Large values near 10^9 still only require checking a fixed number of bits.

Approaches

Brute Force Approach

A brute force approach would attempt all possible combinations of flips on the bits of a and b until finding a configuration where:

(a OR b) == c

For each bit position, there are multiple possibilities:

  • Leave the bit unchanged
  • Flip the bit in a
  • Flip the bit in b
  • Flip both bits

If there are about 30 bits, the number of possible configurations becomes exponential. Exploring every combination would be computationally infeasible.

Although brute force would eventually produce the correct answer because it explores all possibilities, it is far too slow for the given constraints.

Optimal Bit-by-Bit Greedy Approach

The key insight is that OR operates independently on each bit position.

For every bit:

  • If the target bit in c is 1, we only need at least one of the bits in a or b to be 1.
  • If the target bit in c is 0, both bits in a and b must be 0.

This means we can determine the minimum flips needed for each bit independently and sum them together.

For a single bit position:

  • If c_bit == 1

  • If either a_bit or b_bit is already 1, no flips are needed.

  • Otherwise, exactly one flip is needed.

  • If c_bit == 0

  • Any 1 bits in a or b must be flipped to 0.

  • This may require zero, one, or two flips.

Since we only inspect each bit once, the algorithm is extremely efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(4^B) O(1) Tries all possible flip combinations across B bits
Optimal O(B) O(1) Processes each bit independently using bit manipulation

Here, B is the number of bits, approximately 30 for the given constraints.

Algorithm Walkthrough

  1. Initialize a variable flips to 0.
  2. Process the bits of a, b, and c one position at a time.
  3. Extract the least significant bit of each number using:
a_bit = a & 1
b_bit = b & 1
c_bit = c & 1
  1. If c_bit is 1, then the OR result at this position must also be 1.
  • If either a_bit or b_bit is already 1, no action is needed.
  • If both are 0, we must flip one bit from 0 to 1.
  • Add 1 to flips in that case.
  1. If c_bit is 0, then both a_bit and b_bit must become 0.
  • If a_bit is 1, it must be flipped.
  • If b_bit is 1, it must also be flipped.
  • Add a_bit + b_bit to flips.
  1. Shift all three numbers right by one bit:
a >>= 1
b >>= 1
c >>= 1
  1. Continue until all bits have been processed.
  2. Return the accumulated flips.

Why it works

The algorithm works because the OR operation is independent for each bit position. The minimum flips needed at one bit do not affect any other bit. Therefore, computing the optimal answer for each bit separately and summing the results produces the global minimum number of flips.

Python Solution

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0

        while a > 0 or b > 0 or c > 0:
            a_bit = a & 1
            b_bit = b & 1
            c_bit = c & 1

            if c_bit == 1:
                if a_bit == 0 and b_bit == 0:
                    flips += 1
            else:
                flips += a_bit + b_bit

            a >>= 1
            b >>= 1
            c >>= 1

        return flips

The implementation follows the algorithm directly.

The variable flips stores the total number of required bit changes.

Inside the loop, we extract the current least significant bit from each number using bitwise AND with 1. This isolates the current bit position.

When c_bit is 1, we verify whether at least one of a_bit or b_bit is already 1. If both are 0, one flip is required.

When c_bit is 0, every 1 bit in a or b must be removed. Since a_bit and b_bit are either 0 or 1, adding them directly gives the exact number of flips required for that position.

Finally, right shifts move the next bit into the least significant position for processing.

Go Solution

func minFlips(a int, b int, c int) int {
    flips := 0

    for a > 0 || b > 0 || c > 0 {
        aBit := a & 1
        bBit := b & 1
        cBit := c & 1

        if cBit == 1 {
            if aBit == 0 && bBit == 0 {
                flips++
            }
        } else {
            flips += aBit + bBit
        }

        a >>= 1
        b >>= 1
        c >>= 1
    }

    return flips
}

The Go implementation is nearly identical to the Python version.

Go uses explicit variable declarations with :=, and the loop condition uses Go's boolean syntax with ||.

Integer overflow is not a concern because the input constraints are small relative to Go's integer capacity.

Worked Examples

Example 1

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

Binary representations:

a = 010
b = 110
c = 101
Step a_bit b_bit c_bit Action Flips
1 0 0 1 Need one 1, flip one bit 1
2 1 1 0 Both must become 0, flip both 3
3 0 1 1 OR already equals 1 3

Final answer:

3

Example 2

Input: a = 4, b = 2, c = 7

Binary representations:

a = 100
b = 010
c = 111
Step a_bit b_bit c_bit Action Flips
1 0 0 1 Flip one bit to 1 1
2 0 1 1 Already valid 1
3 1 0 1 Already valid 1

Final answer:

1

Example 3

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

Binary representations:

a = 01
b = 10
c = 11
Step a_bit b_bit c_bit Action Flips
1 1 0 1 Already valid 0
2 0 1 1 Already valid 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(B) Processes each bit exactly once
Space O(1) Uses only a few integer variables

Since integers up to 10^9 require at most about 30 bits, the loop runs a constant number of times. This makes the solution extremely efficient in practice.

Test Cases

sol = Solution()

assert sol.minFlips(2, 6, 5) == 3  # Example 1
assert sol.minFlips(4, 2, 7) == 1  # Example 2
assert sol.minFlips(1, 2, 3) == 0  # Example 3

assert sol.minFlips(0, 0, 0) == 0  # All zeros
assert sol.minFlips(0, 0, 1) == 1  # One flip needed
assert sol.minFlips(1, 1, 0) == 2  # Both bits must flip to 0

assert sol.minFlips(8, 3, 5) == 3  # Mixed bit pattern
assert sol.minFlips(7, 7, 7) == 0  # Already equal
assert sol.minFlips(7, 7, 0) == 6  # Every set bit must flip

assert sol.minFlips(1024, 2048, 4096) == 3  # Higher bit positions
assert sol.minFlips(1_000_000_000, 1_000_000_000, 0) > 0  # Large values
Test Why
(2, 6, 5) Validates the main example with mixed operations
(4, 2, 7) Tests creating a missing 1 bit
(1, 2, 3) Tests already valid inputs
(0, 0, 0) Smallest possible values
(0, 0, 1) Requires exactly one flip
(1, 1, 0) Requires two flips at one position
(8, 3, 5) Mixed binary transitions
(7, 7, 7) No changes needed
(7, 7, 0) All set bits must be cleared
(1024, 2048, 4096) Tests higher bit positions
Large values Ensures solution handles upper constraints

Edge Cases

One important edge case occurs when both a and b contain a 1 bit while c contains a 0 bit at the same position. A common mistake is to count this as one flip because the OR result is already 1. However, both bits must become 0, so two flips are required. The implementation handles this correctly by adding a_bit + b_bit.

Another important case is when both a and b contain 0 bits while c contains a 1 bit. In this situation, exactly one flip is sufficient because only one of the two numbers needs a 1 bit. The algorithm correctly increments the answer by one.

A third edge case involves inputs that already satisfy the condition (a OR b) == c. Some implementations may accidentally overcount flips if they do not carefully distinguish between the c_bit == 0 and c_bit == 1 cases. This solution performs no unnecessary operations and correctly returns 0.

Finally, large integers near the upper constraint are handled efficiently because the algorithm processes only individual bits. The runtime remains effectively constant since only about 30 bits must be checked.