1318. Minimum Flips to Make a OR b Equal to c

Description of 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 1:

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

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

Solution

Tags: Bit Manipulation

Explanation - "Truth Table"

We can consider all combinations of each 3-bit by "truth table". Error occur if and only if (a|b) != c. Find those rows in truth table and calculate the number of bits need to be flipped.

"Truth table":
a b c   #flips needs
----------------------
0 0 0    0
0 0 1    1
0 1 0    1
0 1 1    0

1 0 0    1
1 0 1    0
1 1 0    2
1 1 1    0

Code (Rust)

impl Solution {
    pub fn min_flips(a: i32, b: i32, c: i32) -> i32 {
        let (mut a, mut b, mut c) = (a,b,c);
        let mut count = 0;
        while a > 0 || b > 0 || c > 0 {
            match (a%2, b%2, c%2) {
                (0,0,1) | (0,1,0) | (1,0,0) => {count+=1;},
                (1,1,0) => {count+=2;},
                _ => {},
            }
            
            a = a >> 1;
            b = b >> 1;
            c = c >> 1;
        }

        return count;
    }
}

Complexity

let x, y and z be length of a's, b's and c's binary representation

Time Complexity

\(T(n) = O(\max(x,y,z))\)

Auxiliary Space

\(S(n) = O(1)\)

Leetbook