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

Problem: 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:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

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

Approach: Let's try simple approach where we will simply see each bit of a | b and c and decide how many flips we need.

Let's take first example itself:

• a = 2 => 0 1 0
• b = 6 => 1 1 0
• c = 5 => 1 0 1

Let's take the left most bits:

• a => 0
• b => 0
• c => 1

To make a | b 1, we need to flip one of the bits, right so flips required is 1. Now, let's look at the remaining bits:

• a => 0 1
• b => 1 1
• c => 1 0

Again let's see how many flips required to make the left most bits same of a | b and c which are:

• a => 1
• b => 1
• c => 0

Obviously we need to make both a's and b's bits 0 to make it's OR 0 so the number of flips now increased by 2 so the flips required now is 3.

Now again take a look at the remaining bits:

• a => 0
• b => 1
• c => 1

Here if you see a | b is already equal to c. 0 | 1 = 1. That means here we don't need any flip so the final answer is 3.

That is all we are trying to do using coding :)

Implementation in C#:

    public int MinFlips(int a, int b, int c)

    {

        int flips = 0;

        while (a > 0 || b > 0 || c > 0)

        {

            int rightBitA = a & 1;

            int rightBitB = b & 1;

            int rightBitC = c & 1;

            if (rightBitC == 0)

            {

                flips += (rightBitA + rightBitB);

            }

            else

            {

                flips += rightBitA == 0 && rightBitB == 0 ? 1 : 0;

            }

            a >>= 1;

            b >>= 1;

            c >>= 1;

        }

        return flips;

    }

Complexity: O(log(Max(a, b, c))