Minimum Flips to Make a OR b Equal to c

• Convert the integers a, b, and c to their binary string representations.
• Determine the maximum length among the three binary strings.
• Pad the shorter binary strings with leading zeros to make all strings of equal length. This ensures a correct bit-by-bit comparison.
• Initialize a flips counter to zero.
• Iterate through the strings from left to right (from the most significant bit to the least significant bit).
• In each position i, examine the bits (characters) bit_a, bit_b, and bit_c.
• Apply the flip logic:
  • If bit_c is '0', then both bit_a and bit_b must be '0'. Add 1 to flips for each of bit_a or bit_b that is '1'.
  • If bit_c is '1', then bit_a or bit_b (or both) must be '1'. If both are '0', a single flip is required. Add 1 to flips.
• Return the total flips count.

The core idea is to transform the problem from the domain of integer bitwise operations to string manipulation. By converting a, b, and c to binary strings, we can visually inspect each bit position.

For example, if a=2, b=6, c=5, their binary strings are "10", "110", and "101". The maximum length is 3. We pad the strings to get a="010", b="110", c="101". Now we can compare them position by position:

• Position 0 (MSB): a='0', b='1', c='1'. 0|1 = 1. This matches c's bit. 0 flips.
• Position 1: a='1', b='1', c='0'. 1|1 = 1. This does not match c's bit. To make the result '0', both a and b must be '0'. We need to flip a's bit and b's bit. 2 flips.
• Position 2 (LSB): a='0', b='0', c='1'. 0|0 = 0. This does not match c's bit. To make the result '1', we need to flip either a's bit or b's bit. 1 flip.

Total flips = 0 + 2 + 1 = 3.

1class Solution {2    public int minFlips(int a, int b, int c) {3        String aStr = Integer.toBinaryString(a);4        String bStr = Integer.toBinaryString(b);5        String cStr = Integer.toBinaryString(c);6 7        int len = Math.max(aStr.length(), Math.max(bStr.length(), cStr.length()));8 9        // Pad strings with leading zeros10        aStr = String.format("%" + len + "s", aStr).replace(' ', '0');11        bStr = String.format("%" + len + "s", bStr).replace(' ', '0');12        cStr = String.format("%" + len + "s", cStr).replace(' ', '0');13 14        int flips = 0;15        for (int i = 0; i < len; i++) {16            char bitA = aStr.charAt(i);17            char bitB = bStr.charAt(i);18            char bitC = cStr.charAt(i);19 20            if (bitC == '0') {21                if (bitA == '1') flips++;22                if (bitB == '1') flips++;23            } else { // bitC == '1'24                if (bitA == '0' && bitB == '0') {25                    flips++;26                }27            }28        }29        return flips;30    }31}

• Initialize a flips counter to 0.
• Start a loop that continues as long as a, b, or c is greater than 0. This ensures all relevant bits are processed.
• Inside the loop, extract the least significant bit (LSB) of each number using the bitwise AND operator (& 1). Let these be bitA, bitB, and bitC.
• Apply the core logic:
  • If bitC is 0, the result of bitA | bitB must be 0. This requires both bitA and bitB to be 0. The number of flips needed is bitA + bitB (since each '1' bit must be flipped to '0').
  • If bitC is 1, the result of bitA | bitB must be 1. A flip is only needed if both bitA and bitB are 0. In this case, one flip is required.
• Add the calculated flips for the current bit position to the total flips count.
• Right-shift a, b, and c by one position (>>= 1) to process the next bit in the following iteration.
• Once the loop terminates (all numbers are 0), return the total flips.

The problem can be solved by analyzing the bits of a, b, and c at each position i. For the condition (a | b) == c to hold, the condition (a_i | b_i) == c_i must hold for every bit i.

We can iterate through the bits and count the minimum flips required.

• Case 1: Target bit c_i is 1. To make a_i | b_i = 1, we need at least one of a_i or b_i to be 1. If they are currently a_i=0 and b_i=0, we must perform one flip (either 0->1 in a or b). If a_i or b_i is already 1, no flips are needed for this bit. So, we add 1 to flips if (a_i | b_i) == 0.

• Case 2: Target bit c_i is 0. To make a_i | b_i = 0, both a_i and b_i must be 0. If a_i is 1, it must be flipped (1 flip). If b_i is 1, it must also be flipped (1 flip). So, the number of flips is the sum of the bits of a and b at this position.

The algorithm iterates using a while loop, checking the least significant bit (LSB) in each pass with & 1, and then right-shifting the numbers with >>= 1 to process the next bit.

1class Solution {2    public int minFlips(int a, int b, int c) {3        int flips = 0;4        // Loop until all bits of a, b, and c have been processed.5        while (a > 0 || b > 0 || c > 0) {6            // Get the least significant bit of each number7            int bitA = a & 1;8            int bitB = b & 1;9            int bitC = c & 1;10 11            if (bitC == 0) {12                // If c's bit is 0, a's and b's bits must both be 0.13                // Add flips for each bit that is 1.14                flips += (bitA + bitB);15            } else { // bitC == 116                // If c's bit is 1, we need at least one 1 in a or b.17                // If both are 0, we need one flip.18                if (bitA == 0 && bitB == 0) {19                    flips++;20                }21            }22 23            // Move to the next bit24            a >>= 1;25            b >>= 1;26            c >>= 1;27        }28        return flips;29    }30}