Jobs

Interviews

Discussions

Minimum Flips to Make a OR b Equal to c

Medium

Asked by:

5 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Minimum Flips to Make a OR b Equal to c

Medium

Asked by:

5 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values of a, b, and c?
Are a, b, and c guaranteed to be non-negative?
If there are multiple ways to achieve the minimum number of flips, is any of them acceptable?
Are we optimizing for space complexity, or just time complexity?
Could you provide a few examples to ensure I fully understand the expected behavior?

Brute Force Solution

Approach

The goal is to figure out the fewest changes needed to make two numbers, after combining them in a specific way, equal to a third number. The brute-force way means we're going to check every single possible combination of changes to the first two numbers.

Here's how the algorithm would work step-by-step:

Consider the first number and the second number. Each of these numbers is made up of individual 'bits' (think of them like light switches that are either on or off).
Go through each 'bit' position in the numbers, one by one, from right to left.
For each 'bit' position, try all the possible combinations of changing (flipping) the 'bits' in the first and second numbers. You could flip none, flip the first, flip the second, or flip both.
For each of these combinations of flips, see if the result of combining the flipped 'bits' in the first and second numbers matches the corresponding 'bit' in the third number.
Keep track of how many flips it took for each combination to make the combination match. Also keep track of the total number of flips required across all bit positions.
After checking every possible combination of flips for every 'bit' position, pick the combination that required the fewest total flips. That's your answer.

Code Implementation

def min_flips_brute_force(a_input, b_input, c_input):
    minimum_flips = float('inf')
    for i in range(1 << 30):
        for j in range(1 << 30):
            a_temp = a_input
            b_temp = b_input
            flips = 0
            for bit_position in range(30):
                a_bit = (a_input >> bit_position) & 1
                b_bit = (b_input >> bit_position) & 1
                c_bit = (c_input >> bit_position) & 1
                a_flip = (i >> bit_position) & 1
                b_flip = (j >> bit_position) & 1

                if a_flip:
                    a_temp ^= (1 << bit_position)
                    flips += 1
                if b_flip:
                    b_temp ^= (1 << bit_position)
                    flips += 1

                # Check if after flips (a OR b) == c
                if ((a_temp >> bit_position) & 1) | ((b_temp >> bit_position) & 1) != c_bit:
                    flips = float('inf')
                    break

            # Store if the current flips are lower than the current minimum
            minimum_flips = min(minimum_flips, flips)

    if minimum_flips == float('inf'):
        return -1
    return minimum_flips

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through the bits of the numbers a, b, and c. Since integers have a fixed number of bits (e.g., 32 bits for a 32-bit integer), the number of iterations is constant regardless of the magnitude of the input numbers. For each bit position, it considers a fixed number of flip combinations (at most 4). Therefore, the time complexity is constant, denoted as O(1).

Space Complexity

O(1) – The brute-force approach iterates through each bit of the input numbers a, b, and c. The explanation mentions trying all combinations of flips, but it doesn't explicitly state the use of any auxiliary data structures to store these combinations or intermediate results. It only implies calculating the number of flips and keeping track of the minimum. Therefore, only a few constant space variables are likely used to store the current number of flips, the minimum number of flips found so far, and possibly loop counters, which means the space used is independent of the size of the input numbers. Hence, the space complexity is constant.

Optimal Solution

Approach

The key is to examine each bit position of the numbers individually. We can determine the minimum flips needed at each bit by comparing the corresponding bits in the input numbers and the target number.

Here's how the algorithm would work step-by-step:

Go through each bit position from right to left (least significant to most significant) for all three numbers.
Look at the current bits of the two input numbers. Consider their relationship to the corresponding bit of the target number.
If the target bit is 1: We need a 1. If either of the input bits is already a 1, no flip is needed. If both input bits are 0, we need to flip one of them to a 1.
If the target bit is 0: We need a 0. This means both input bits must be 0. If either of the input bits are 1, they must be flipped. If both input bits are 1, we must flip both to 0.
Count the number of flips needed for each bit position.
The total number of flips is the sum of the flips needed for each bit position. That's our final answer.

Code Implementation

def minimum_flips(a, b, c):
    flip_count = 0

    # Iterate through the bits of the numbers
    for i in range(32):
        bit_a = (a >> i) & 1
        bit_b = (b >> i) & 1
        bit_c = (c >> i) & 1

        # Check if the target bit is 1
        if bit_c == 1:
            # If both bits are 0, we need to flip one
            if bit_a == 0 and bit_b == 0:
                flip_count += 1

        # Check if the target bit is 0
        else:
            # If either bit is 1, we need to flip it
            if bit_a == 1 and bit_b == 1:
                # Both must be flipped if c is 0, a and b are 1
                flip_count += 2

            elif bit_a == 1 or bit_b == 1:
                # One of them must be flipped
                flip_count += 1

    return flip_count

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through the bits of the input integers a, b, and c. Since integers have a fixed number of bits (typically 32 or 64), the number of iterations is constant and independent of the magnitude of the input numbers. Therefore, the time complexity is O(1) because the number of operations doesn't grow with increasing input size; it's capped by the number of bits in an integer, a constant.

Space Complexity

O(1) – The provided algorithm operates bitwise on the input integers a, b, and c. It does not use any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. The operations are performed in place using a constant number of variables to track the bitwise comparisons and the flip count. Therefore, the space complexity is independent of the input size and remains constant.

Edge Cases

Case	How to Handle
a, b, and c are all 0	The algorithm should correctly return 0 since the bitwise OR of 0 and 0 is already 0.
a and b are 0, but c is a large positive number	The solution must accurately count the number of '1' bits in 'c' as flips needed for 'a' and 'b'.
a and b are large positive numbers, but c is 0	The algorithm must accurately count the number of flips needed to turn '1' bits in 'a' and 'b' to '0'.
Integer Overflow: a, b, or c is close to the maximum integer value (2^31 - 1)	The bitwise operations should handle large integers correctly within the standard integer range, and we avoid intermediate results that may cause overflows during bitwise comparisons and counting.
a and b have many overlapping set bits, and c has few set bits	The algorithm needs to consider the case where both a and b need to be flipped if the corresponding bit in c is 0, even if either a or b originally had that bit set.
a, b, c are all the same number, but not 0	If a \| b == c initially, the result should be 0 flips; otherwise, we need to check if we can make a \| b == c with a minimal number of flips.
c has a bit set to 1 where both a and b have that bit set to 0.	At least one of a or b needs a flip at that bit position.
c has a bit set to 0 where both a and b have that bit set to 1.	Both a and b need a flip at that bit position.

a, b, and c are all 0

How to Handle:

The algorithm should correctly return 0 since the bitwise OR of 0 and 0 is already 0.

a and b are 0, but c is a large positive number

How to Handle:

The solution must accurately count the number of '1' bits in 'c' as flips needed for 'a' and 'b'.

a and b are large positive numbers, but c is 0

How to Handle:

The algorithm must accurately count the number of flips needed to turn '1' bits in 'a' and 'b' to '0'.

Integer Overflow: a, b, or c is close to the maximum integer value (2^31 - 1)

How to Handle:

The bitwise operations should handle large integers correctly within the standard integer range, and we avoid intermediate results that may cause overflows during bitwise comparisons and counting.

a and b have many overlapping set bits, and c has few set bits

How to Handle:

The algorithm needs to consider the case where both a and b need to be flipped if the corresponding bit in c is 0, even if either a or b originally had that bit set.

a, b, c are all the same number, but not 0

How to Handle:

If a | b == c initially, the result should be 0 flips; otherwise, we need to check if we can make a | b == c with a minimal number of flips.

c has a bit set to 1 where both a and b have that bit set to 0.

How to Handle:

At least one of a or b needs a flip at that bit position.

c has a bit set to 0 where both a and b have that bit set to 1.

How to Handle:

Both a and b need a flip at that bit position.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer values of a, b, and c?
Are a, b, and c guaranteed to be non-negative?
If there are multiple ways to achieve the minimum number of flips, is any of them acceptable?
Are we optimizing for space complexity, or just time complexity?
Could you provide a few examples to ensure I fully understand the expected behavior?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first number and the second number. Each of these numbers is made up of individual 'bits' (think of them like light switches that are either on or off).
Go through each 'bit' position in the numbers, one by one, from right to left.
For each 'bit' position, try all the possible combinations of changing (flipping) the 'bits' in the first and second numbers. You could flip none, flip the first, flip the second, or flip both.
For each of these combinations of flips, see if the result of combining the flipped 'bits' in the first and second numbers matches the corresponding 'bit' in the third number.
Keep track of how many flips it took for each combination to make the combination match. Also keep track of the total number of flips required across all bit positions.
After checking every possible combination of flips for every 'bit' position, pick the combination that required the fewest total flips. That's your answer.

Code Implementation

def min_flips_brute_force(a_input, b_input, c_input):
    minimum_flips = float('inf')
    for i in range(1 << 30):
        for j in range(1 << 30):
            a_temp = a_input
            b_temp = b_input
            flips = 0
            for bit_position in range(30):
                a_bit = (a_input >> bit_position) & 1
                b_bit = (b_input >> bit_position) & 1
                c_bit = (c_input >> bit_position) & 1
                a_flip = (i >> bit_position) & 1
                b_flip = (j >> bit_position) & 1

                if a_flip:
                    a_temp ^= (1 << bit_position)
                    flips += 1
                if b_flip:
                    b_temp ^= (1 << bit_position)
                    flips += 1

                # Check if after flips (a OR b) == c
                if ((a_temp >> bit_position) & 1) | ((b_temp >> bit_position) & 1) != c_bit:
                    flips = float('inf')
                    break

            # Store if the current flips are lower than the current minimum
            minimum_flips = min(minimum_flips, flips)

    if minimum_flips == float('inf'):
        return -1
    return minimum_flips

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Go through each bit position from right to left (least significant to most significant) for all three numbers.
Look at the current bits of the two input numbers. Consider their relationship to the corresponding bit of the target number.
If the target bit is 1: We need a 1. If either of the input bits is already a 1, no flip is needed. If both input bits are 0, we need to flip one of them to a 1.
If the target bit is 0: We need a 0. This means both input bits must be 0. If either of the input bits are 1, they must be flipped. If both input bits are 1, we must flip both to 0.
Count the number of flips needed for each bit position.
The total number of flips is the sum of the flips needed for each bit position. That's our final answer.

Code Implementation

def minimum_flips(a, b, c):
    flip_count = 0

    # Iterate through the bits of the numbers
    for i in range(32):
        bit_a = (a >> i) & 1
        bit_b = (b >> i) & 1
        bit_c = (c >> i) & 1

        # Check if the target bit is 1
        if bit_c == 1:
            # If both bits are 0, we need to flip one
            if bit_a == 0 and bit_b == 0:
                flip_count += 1

        # Check if the target bit is 0
        else:
            # If either bit is 1, we need to flip it
            if bit_a == 1 and bit_b == 1:
                # Both must be flipped if c is 0, a and b are 1
                flip_count += 2

            elif bit_a == 1 or bit_b == 1:
                # One of them must be flipped
                flip_count += 1

    return flip_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
a, b, and c are all 0	The algorithm should correctly return 0 since the bitwise OR of 0 and 0 is already 0.
a and b are 0, but c is a large positive number	The solution must accurately count the number of '1' bits in 'c' as flips needed for 'a' and 'b'.
a and b are large positive numbers, but c is 0	The algorithm must accurately count the number of flips needed to turn '1' bits in 'a' and 'b' to '0'.
Integer Overflow: a, b, or c is close to the maximum integer value (2^31 - 1)	The bitwise operations should handle large integers correctly within the standard integer range, and we avoid intermediate results that may cause overflows during bitwise comparisons and counting.
a and b have many overlapping set bits, and c has few set bits	The algorithm needs to consider the case where both a and b need to be flipped if the corresponding bit in c is 0, even if either a or b originally had that bit set.
a, b, c are all the same number, but not 0	If a \| b == c initially, the result should be 0 flips; otherwise, we need to check if we can make a \| b == c with a minimal number of flips.
c has a bit set to 1 where both a and b have that bit set to 0.	At least one of a or b needs a flip at that bit position.
c has a bit set to 0 where both a and b have that bit set to 1.	Both a and b need a flip at that bit position.

a, b, and c are all 0

How to Handle:

The algorithm should correctly return 0 since the bitwise OR of 0 and 0 is already 0.

a and b are 0, but c is a large positive number

How to Handle:

The solution must accurately count the number of '1' bits in 'c' as flips needed for 'a' and 'b'.

a and b are large positive numbers, but c is 0

How to Handle:

The algorithm must accurately count the number of flips needed to turn '1' bits in 'a' and 'b' to '0'.

Integer Overflow: a, b, or c is close to the maximum integer value (2^31 - 1)

How to Handle:

The bitwise operations should handle large integers correctly within the standard integer range, and we avoid intermediate results that may cause overflows during bitwise comparisons and counting.

a and b have many overlapping set bits, and c has few set bits

How to Handle:

The algorithm needs to consider the case where both a and b need to be flipped if the corresponding bit in c is 0, even if either a or b originally had that bit set.

a, b, c are all the same number, but not 0

How to Handle:

If a | b == c initially, the result should be 0 flips; otherwise, we need to check if we can make a | b == c with a minimal number of flips.

c has a bit set to 1 where both a and b have that bit set to 0.

How to Handle:

At least one of a or b needs a flip at that bit position.

c has a bit set to 0 where both a and b have that bit set to 1.

How to Handle:

Both a and b need a flip at that bit position.