Course4all
Join us on telegram
Home/dsa/Bit Manipulation/Minimum Flips to Make a OR b Equal to c

Minimum Flips to Make a OR b Equal to c

Master this topic with zero to advance depth.

Minimum Flips to Make a OR b Equal to c

Given 3 positives a, b and c. Return the minimum flips required in some bits of a and b to make (a OR b == c).

Medium

Examples

Input: a = 2, b = 6, c = 5
Output: 3
Input: a = 4, b = 2, c = 7
Output: 1
Approach 1

Level I: Brute Force (Bit-by-Bit Check)

Intuition

Iterate through each bit of the three numbers and compare the required state c with the current state a | b. Count the flips needed for each bit position.

Thought Process

  1. For each bit position ii (0 to 31):
    • If ii-th bit of c is 0:
      • Both ii-th bits of a and b must be 0. Add their sum to flips.
    • If ii-th bit of c is 1:
      • At least one of ii-th bits of a or b must be 1. If both are 0, add 1 to flips.
  2. Return flips.

Pattern: Positional Verification

⏱ O(1) - Always 32 iterations.💾 O(1) - Constant space.
java
public class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; i++) {
            int bitA = (a >> i) & 1;
            int bitB = (b >> i) & 1;
            int bitC = (c >> i) & 1;
            if (bitC == 0) {
                flips += (bitA + bitB);
            } else {
                if (bitA == 0 && bitB == 0) flips++;
            }
        }
        return flips;
    }
}
Approach 2

Level II: Iterative with Built-in Counting

Intuition

Instead of checking every bit manually, we can use built-in bit counting functions to calculate the flips needed for the entire numbers after identifying which bits are incorrect via XOR and AND.

⏱ $O(1)$💾 $O(1)$
java
class Solution {
    public int minFlips(int a, int b, int c) {
        int res = 0;
        for (int i = 0; i < 31; i++) {
            int bitA = (a >> i) & 1, bitB = (b >> i) & 1, bitC = (c >> i) & 1;
            if (bitC == 0) res += bitA + bitB;
            else if (bitA + bitB == 0) res += 1;
        }
        return res;
    }
}
Approach 3

Level III: Optimal (Bitwise Magic)

Intuition

We can use bitwise operators to find all differing bits at once. (a | b) ^ c gives bits that are incorrect. We then handle the cases where c bit is 0 separately as they might require 2 flips per bit.

Thought Process

  1. incorrect = (a | b) ^ c.
  2. must_flip_two = a & b & incorrect.
  3. Flips = Count of set bits in incorrect + Count of set bits in must_flip_two.

Pattern: Composite Bitmasking

⏱ O(1) - Constant number of bitwise operations.💾 O(1) - Constant space.

Detailed Dry Run

a=2(0010), b=6(0110), c=5(0101) a|b = 6 (0110) incorrect = 0110 ^ 0101 = 0011 (bits 0 and 1 are wrong) must_flip_two = 0010 & 0110 & 0011 = 0010 (bit 1 is wrong and both a,b are 1) Total = popcount(0011) + popcount(0010) = 2 + 1 = 3.

java
public class Solution {
    public int minFlips(int a, int b, int c) {
        return Integer.bitCount((a | b) ^ c) + Integer.bitCount(a & b & ((a | b) ^ c));
    }
}
← Previous QuestionTotal Hamming Distance
Next Question →Sum of All Subset XOR Totals