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

Description

The problem involves finding the minimum number of bit flips required to make the bitwise OR of two integers a and b equal to a third integer c. Each bit in a, b, and c is examined individually, and based on the value of each bit, the number of operations required to achieve the desired outcome is calculated.

Intuition

The key insight is to recognize that for each bit position, we can determine the necessary operations by comparing the bits of a, b, and c. If the bit in c is 1, at least one of the corresponding bits in a or b must be 1. If the bit in c is 0, both corresponding bits in a and b must be 0. The number of flips required is based on whether these conditions are met.

Approach

1. Initialize a counter to track the number of operations (bit flips).
2. Use a loop to iterate through each bit position of a, b, and c until all bits have been processed.
3. For each bit: - If the bit in c is 1, check if both bits in a and b are 0. If so, one flip is required. - If the bit in c is 0, check if either bit in a or b is 1. If so, flips are required to turn them to 0.
4. Shift a, b, and c right by one bit after each iteration to process the next bit.
5. Continue until all bits have been processed and return the total number of operations.

Complexity

Time Complexity:

O(log(max(a, b, c))) where log(max(a, b, c)) represents the number of bits required to represent the largest number among a, b, and c. Each bit is processed in constant time.

Space Complexity:

O(1) since only a few variables are used, and no additional space is required beyond the input size.

Code

C++

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int operations = 0;
        while (a > 0 || b > 0 || c > 0) {
            if (c & 1) {
                if (!(a & 1 || b & 1)) {
                    operations++;
                }
            } else {
                if (a & 1) {
                    operations++;
                }
                if (b & 1) {
                    operations++;
                }
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return operations;
    }
};

Python

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        operations = 0
        while a > 0 or b > 0 or c > 0:
            if c & 1:
                if not (a & 1 or b & 1):
                    operations += 1
            else:
                if a & 1:
                    operations += 1
                if b & 1:
                    operations += 1
            a >>= 1
            b >>= 1
            c >>= 1

        return operations

Java

class Solution {
    public int minFlips(int a, int b, int c) {
        int operations = 0;
        while (a > 0 || b > 0 || c > 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    operations++;
                }
            } else {
                if ((a & 1) == 1) {
                    operations++;
                }
                if ((b & 1) == 1) {
                    operations++;
                }
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return operations;
    }
}

JavaScript

var minFlips = function(a, b, c) {
    let operations = 0;
    while (a > 0 || b > 0 || c > 0) {
        if (c & 1) {
            if (!(a & 1 || b & 1)) {
                operations++;
            }
        } else {
            if (a & 1) {
                operations++;
            }
            if (b & 1) {
                operations++;
            }
        }
        a >>= 1;
        b >>= 1;
        c >>= 1;
    }

    return operations;
};