#1318 - Minimum Flips to Make a OR b Equal to c

MediumBit Manipulation

Given three positive integers a, b, and c, return the minimum number of bit flips required so that a OR b === c. A flip changes a single bit from 0 to 1 or 1 to 0 in either a or b.

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

Solution Space

Try it

/**
 * Returns the minimum bit flips in a and/or b so that (a OR b) === c.
 *
 * For each bit position:
 * - c bit is 1: need at least one of a,b to be 1 → if both are 0, flip one (1 flip).
 * - c bit is 0: both a,b must be 0 → flip each 1-bit (could be 1 or 2 flips).
 *
 * @param a First integer
 * @param b Second integer
 * @param c Target OR result
 * @returns Minimum number of flips
 */
export function minFlips(a: number, b: number, c: number): number {
  let flips = 0;

  while (a > 0 || b > 0 || c > 0) {
    const bitA = a & 1;
    const bitB = b & 1;
    const bitC = c & 1;

    if (bitC === 1) {
      if (bitA === 0 && bitB === 0) flips += 1; // need one 1
    } else {
      flips += bitA + bitB; // both must be 0; flip each 1
    }

    a >>= 1;
    b >>= 1;
    c >>= 1;
  }

  return flips;
}

Approach: bit-by-bit comparison – inspect each bit position: if `c` bit is 1, ensure at least one of `a`/`b` is 1; if `c` bit is 0, flip every 1 in `a` and `b` at that position.

Time: O(max(log a, log b, log c)) – processes up to ~30 bits.

Space: O(1) – a few variables.

#338 Counting Bits

#208 Implement Trie (Prefix Tree)