{x}
blog image

Minimum Flips to Make a OR b Equal to c

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 Explanation for Minimum Flips to Make a OR b Equal to c

This problem asks to find the minimum number of bit flips needed in integers a and b such that their bitwise OR (a | b) equals c.

Approach:

The solution iterates through each bit position (0 to 31 for 32-bit integers). For each bit position, we examine the corresponding bits in a, b, and c. Let's denote these bits as x, y, and z respectively. We analyze the following cases:

  1. z is 0: If the corresponding bit in c is 0, then both x and y must be 0. If either x or y (or both) are 1, we need to flip those bits to 0. The number of flips required is x + y.

  2. z is 1: If the corresponding bit in c is 1, then at least one of x or y must be 1. However, if both x and y are 0, we need to flip one of them to 1 (one flip is required).

The code sums up the flips required for each bit position to get the total minimum flips.

Time Complexity: O(log M), where M is the maximum value among a, b, and c. This is because we iterate through the bits of the integers, and the number of bits is logarithmic with respect to the magnitude of the integer.

Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python):

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 (1 if x == 0 and y == 0 else 0)  # concise expression for the logic
        return ans

Code Implementation (Java):

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;
            int y = (b >> i) & 1;
            int z = (c >> i) & 1;
            if (z == 0) {
                ans += x + y;
            } else if (x == 0 && y == 0) {
                ans++;
            }
        }
        return ans;
    }
}

Code Implementation (C++):

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;
            int y = (b >> i) & 1;
            int z = (c >> i) & 1;
            if (z == 0) {
                ans += x + y;
            } else if (x == 0 && y == 0) {
                ans++;
            }
        }
        return ans;
    }
};

Code Implementation (Go):

func minFlips(a int, b int, c int) int {
	ans := 0
	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 ans
}

Code Implementation (Typescript):

function minFlips(a: number, b: number, c: number): number {
    let ans = 0;
    for (let i = 0; i < 32; i++) {
        const x = (a >> i) & 1;
        const y = (b >> i) & 1;
        const z = (c >> i) & 1;
        if (z === 0) {
            ans += x + y;
        } else if (x === 0 && y === 0) {
            ans++;
        }
    }
    return ans;
}

All the code examples implement the same bit manipulation approach and have the same time and space complexity. They differ only in syntax.