Skip to content

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

Description

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

Solutions

Solution 1: Bit Manipulation

We can enumerate each bit of the binary representation of \(a\), \(b\), and \(c\), denoted as \(x\), \(y\), and \(z\) respectively. If the bitwise OR operation result of \(x\) and \(y\) is different from \(z\), we then check if both \(x\) and \(y\) are \(1\). If so, we need to flip twice, otherwise, we only need to flip once. We accumulate all the required flip times.

The time complexity is \(O(\log M)\), where \(M\) is the maximum value of the numbers in the problem. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        ans = 0
        for i in range(32):
            x, y, z = a >> i & 1, b >> i & 1, c >> i & 1
            ans += x + y if z == 0 else int(x == 0 and y == 0)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int x = a >> i & 1, y = b >> i & 1, z = c >> i & 1;
            ans += z == 0 ? x + y : (x == 0 && y == 0 ? 1 : 0);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    int minFlips(int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int x = a >> i & 1, y = b >> i & 1, z = c >> i & 1;
            ans += z == 0 ? x + y : (x == 0 && y == 0 ? 1 : 0);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minFlips(a int, b int, c int) (ans int) {
    for i := 0; i < 32; i++ {
        x, y, z := a>>i&1, b>>i&1, c>>i&1
        if z == 0 {
            ans += x + y
        } else if x == 0 && y == 0 {
            ans++
        }
    }
    return
}

1
2
3
4
5
6
7
8
function minFlips(a: number, b: number, c: number): number {
    let ans = 0;
    for (let i = 0; i < 32; ++i) {
        const [x, y, z] = [(a >> i) & 1, (b >> i) & 1, (c >> i) & 1];
        ans += z === 0 ? x + y : x + y === 0 ? 1 : 0;
    }
    return ans;
}

Comments