[LeetCode] 1318. Minimum Flips to Make a OR b Equal to c

1. Question

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
 

2. Thoughts

Use Bit manipulation.

3. Tips learned

4. My solution

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        bin_a, bin_b, bin_c = bin(a)[2:], bin(b)[2:], bin(c)[2:]
        length = max(len(bin_a), len(bin_b), len(bin_c))

        for i in range(1, length + 1):
            temp_a = bin_a[-i] if len(bin_a) >= i else "0"
            temp_b = bin_b[-i] if len(bin_b) >= i else "0"
            temp_c = bin_c[-i] if len(bin_c) >= i else "0"

            if temp_c == "1":
                if temp_a == "0" and temp_b == "0":
                    flips += 1
            else:
                if temp_a == "1":
                    flips += 1
                if temp_b == "1":
                    flips += 1

        return flips

64/64 cases passed (28 ms)
Your runtime beats 95.61 % of python3 submissions
Your memory usage beats 23.09 % of python3 submissions (17.4 MB)

5. AI Solution and Improvements

Your solution to the problem of finding the minimum number of flips in the bits of a and b to make a OR b == c is on the right track, but it can be optimized and simplified. Instead of converting the numbers to their binary string representations, you can directly work with the bits of the integers. This approach is more efficient and aligns better with the nature of the problem, which is inherently bitwise.

Here's an optimized version of your solution:

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        while a > 0 or b > 0 or c > 0:
            bit_a = a & 1
            bit_b = b & 1
            bit_c = c & 1

            # Case when c's bit is 0: both a and b must be flipped if they are 1.
            if bit_c == 0:
                flips += bit_a + bit_b
            # Case when c's bit is 1: one flip needed if both a and b are 0.
            else:
                flips += (bit_a | bit_b) ^ 1

            # Right shift a, b, and c to check the next bit.
            a >>= 1
            b >>= 1
            c >>= 1

        return flips

Explanation:

• The loop runs until all bits in a, b, and c have been checked. This is done by continuously right-shifting (>>= 1) these numbers until they become zero.
• In each iteration, we isolate the least significant bit (LSB) of a, b, and c using the bitwise AND operation (& 1).
• We then check two cases:
  • If bit_c is 0, both bit_a and bit_b must be 0. If either is 1, it needs to be flipped, so we add bit_a + bit_b to flips.
  • If bit_c is 1, at least one of bit_a or bit_b must be 1. If both are 0, we need one flip, so we add (bit_a | bit_b) ^ 1 to flips.
• After checking each bit, we right-shift a, b, and c to move to the next most significant bit.

This approach efficiently computes the minimum flips required using bitwise operations and avoids the overhead of converting integers to binary strings.