Minimum Flips to Make a OR b Equal to c

Problem Description

Welcome to the world of bit manipulation, where we flip bits like pancakes on a Sunday morning! The problem at hand is to determine the minimum number of flips required to make the bitwise OR of two integers a and b equal to another integer c.

Imagine you have two light switches (representing a and b) and a target light (representing c). Your goal is to flip the switches in such a way that the light turns on exactly when you want it to. If both switches are off, the light is off. If at least one switch is on, the light is on. Sounds simple, right? Well, it’s not as easy as it seems!


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

        for i in range(kMaxBit):
            if c >> i & 1:
                ans += (a >> i & 1) == 0 and (b >> i & 1) == 0
            else:  # (c >> i & 1) == 0
                ans += (a >> i & 1) + (b >> i & 1)

        return ans

Approach Explanation

The code works by iterating through each bit position (up to 30 bits, because we’re dealing with integers). For each bit, it checks if the corresponding bit in c is set (i.e., is 1). If it is, it checks if both a and b have that bit unset (0). If both are 0, we need to flip at least one of them to make the OR operation yield 1.

If the bit in c is not set (0), it counts how many of a and b have that bit set (1) and adds that to the answer since we need to flip those bits to make the OR operation yield 0.

Time and Space Complexity

Complexity Type Complexity
Time Complexity O(1) – The loop runs a constant number of times (30), regardless of the input size.
Space Complexity O(1) – We are using a fixed amount of space for variables.

Real-World Example

Let’s say you’re at a party, and you have two friends, Alice and Bob. You want to make sure that at least one of them is dancing (which represents the OR operation). If neither of them is dancing, you need to convince one of them to get up and shake it! If both are dancing, you’re all set. If both are sitting down, you need to flip one of them to get them moving. This is essentially what the problem is asking you to do with bits!

Similar Problems