Scale Engineer

Minimum Flips to Make a OR b Equal to c

Med
#1227Time: O(log N), where N is the maximum value among a, b, and c. The complexity is dominated by the string conversion and the loop that iterates through the bits. This is asymptotically efficient, but carries significant overhead.Space: O(log N), where N is the maximum value among a, b, and c. This space is used to store the binary string representations of the numbers.
Patterns
Bit Manipulation

Prompt

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:

a

Example 2:

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

Example 3:

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

 

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first converts the integers into their binary string representations. To compare them bit by bit, the strings are padded with leading zeros to ensure they all have the same length. Then, we can iterate through the characters of the strings, representing the bits, and count the necessary flips based on the problem's logic.

Algorithm

  • 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.

Walkthrough

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.

class Solution {    public int minFlips(int a, int b, int c) {        String aStr = Integer.toBinaryString(a);        String bStr = Integer.toBinaryString(b);        String cStr = Integer.toBinaryString(c);         int len = Math.max(aStr.length(), Math.max(bStr.length(), cStr.length()));         // Pad strings with leading zeros        aStr = String.format("%" + len + "s", aStr).replace(' ', '0');        bStr = String.format("%" + len + "s", bStr).replace(' ', '0');        cStr = String.format("%" + len + "s", cStr).replace(' ', '0');         int flips = 0;        for (int i = 0; i < len; i++) {            char bitA = aStr.charAt(i);            char bitB = bStr.charAt(i);            char bitC = cStr.charAt(i);             if (bitC == '0') {                if (bitA == '1') flips++;                if (bitB == '1') flips++;            } else { // bitC == '1'                if (bitA == '0' && bitB == '0') {                    flips++;                }            }        }        return flips;    }}

Complexity

Time

O(log N), where N is the maximum value among a, b, and c. The complexity is dominated by the string conversion and the loop that iterates through the bits. This is asymptotically efficient, but carries significant overhead.

Space

O(log N), where N is the maximum value among a, b, and c. This space is used to store the binary string representations of the numbers.

Trade-offs

Pros

  • May be more intuitive for developers who are less comfortable with direct bitwise manipulation.

  • The logic is explicit and follows a clear, readable flow.

Cons

  • Inefficient use of memory due to the creation of intermediate strings.

  • Slower performance because of the overhead associated with string conversions and manipulations compared to direct integer arithmetic.

Solutions

class Solution {public  int minFlips(int a, int b, int c) {    int ans = 0;    for (int i = 0; i < 30; ++i) {      int x = a >> i & 1, y = b >> i & 1, z = c >> i & 1;      if ((x | y) != z) {        ans += x == 1 && y == 1 ? 2 : 1;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem