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

MediumBit Manipulation

Problem Description

In this problem, we are given three positive integers a, b, and c. We need to determine the minimum number of flips required to make the bitwise OR of a and b equal to c. A flip means changing a single bit from 1 to 0 or from 0 to 1 in the binary representation of a or b.

To understand the problem better, let's consider what a bitwise OR operation does. For each bit position in two numbers, the OR operation yields 1 if either of the corresponding bits in the two numbers is 1; otherwise, it yields 0. Therefore, for a | b to become c, each bit position in a or b must be manipulated so that this rule holds true.

Intuition

The intuition behind the solution is to compare the bits of a, b, and c in each corresponding position and determine if a flip is needed. To do this, we iterate through each bit position of the given numbers from the least significant bit to the most significant bit.

For each bit position i, if the ith bit of a OR b does not match the ith bit of c, we must flip bits in a or b to match c. There are a couple of scenarios to consider:

If both a and b have 1 at the ith bit, and c has 0, we must flip both bits in a and b, resulting in two flips.
In any other case where a | b and c do not match (for example, one of a or b is 1 and c is 0, or both a and b are 0 and c is 1), a single flip is sufficient.

By checking these conditions for each bit position, we can accumulate the total number of flips required. The function continues this process for up to 30 bits (since the numbers are positive, which in most systems means we don't need to consider the sign bit and any bits beyond 30 are likely to be zero in common settings), and then returns the total count of flips.

Solution Approach

The algorithm uses a straightforward approach to solve the problem by performing bit manipulation to tally the flips required to make a | b == c. The solution does not require any complex data structures or design patterns, rather it capitalizes on bitwise operations and logical reasoning. Here's the breakdown of the solution approach:

Initialize a variable ans to keep track of the number of flips needed.
Iterate over each bit position (from 0 to 29) to examine individual bits of a, b, and c. The range is up to 30 to cover typical 32-bit integers without the sign bit.
For each iteration, use the right-shift operator >> to move the ith bit to the least significant bit position, then use the bitwise AND operator & with 1 to extract the value of that bit for a, b, and c. This results in three variables x, y, and z representing the ith bits of a, b, and c, respectively.
Use the bitwise OR operator | to determine the result of x | y and compare it to z. If they are not equal, flips are required:
- If both x and y are 1 and z is 0, it means both bits in a and b must be flipped, hence ans is incremented by 2.
- In any other case where a flip is needed (such as when one of a or b has a 1 and c has a 0, or both a and b have a 0 and c has a 1), only 1 flip is necessary, so ans is incremented by 1.
The loop continues until all bits have been considered.
The ans variable, which now holds the total number of flips needed, is returned.

Here is the critical part of the code that encapsulates the described solution approach:

for i in range(30):
    x, y, z = a >> i & 1, b >> i & 1, c >> i & 1
    if x | y != z:
        ans += 2 if x == 1 and y == 1 else 1

This solution effectively uses the fundamental principles of bitwise operations to solve the problem in an efficient and direct manner.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach using the given content.

Assume the input for the problem is a = 5, b = 3, and c = 2. In binary, these numbers are represented as follows:

a = 5 = 101 (binary)
b = 3 = 011 (binary)
c = 2 = 010 (binary)

We need to determine the minimum number of flips required to make a | b equal to c.

The bitwise OR of a and b (a | b) is 101 | 011 = 111 (binary), which equals 7 in decimal. This does not match c = 2 (010 in binary), so we need flips to make it equal.

Now, let's apply the solution step by step:

We initialize a variable ans to 0 to keep count of the number of flips needed.
We start iterating through each bit position from the 0th to the 29th (we won't actually go up to 29 since our numbers are small).
For each iteration (for each bit), we right-shift a, b, and c by i positions and then AND them with 1 to extract the ith bit.

For example, at i = 0 (least significant bit):

x = a >> 0 & 1 is 1 (from 101 last bit)
y = b >> 0 & 1 is 1 (from 011 last bit)
z = c >> 0 & 1 is 0 (from 010 last bit)

We then check if x | y equals z. If it does not, we find the number of flips required.

Continuing our example:

At i = 0: x | y is 1 which doesn't equal z (0). Both x and y are 1 and z is 0, so we must flip both bits from 1 to 0. Thus, we add 2 to ans.

We carry forward with the process:

At i = 1: x = 0, y = 1, z = 1. Here, x | y equals z, so no flip is needed.
At i = 2: x = 1, y = 0, z = 0. Here, x | y does not equal z, and since only x is 1, we add 1 flip to ans.

Since the example uses small numbers, we don't need to go up to i = 29.

After checking all the bits, we find that the ans became 3 (two flips for i = 0 and one flip for i = 2).

Thus, to make a | b equal to c, a minimum of 3 flips are needed.

This step-by-step walkthrough shows how bitwise operations are used to find the number of flips required to match the bitwise OR of two numbers to a third number. The process is simple yet effective, leveraging basic operations to arrive at the solution.

Solution Implementation

1class Solution:
2    def minFlips(self, num_a: int, num_b: int, num_c: int) -> int:
3        # Initialize answer to count the minimum number of flips
4        min_flips = 0
5        # Iterate through each bit position (0 to 29) since the problem states 32-bit integers
6        for i in range(30):
7            # Extract the i-th bit of num_a, num_b, and num_c
8            bit_a = num_a >> i & 1
9            bit_b = num_b >> i & 1
10            bit_c = num_c >> i & 1
11
12            # If the OR of bit_a and bit_b is not equal to bit_c, we need to flip bits
13            if bit_a | bit_b != bit_c:
14                # If both bit_a and bit_b are set (1), we need to flip both to make the OR result match bit_c
15                # which is 0 in this case. This counts as two flips.
16                if bit_a == 1 and bit_b == 1:
17                    min_flips += 2
18                # Otherwise, we only need to flip one bit to match the OR result to bit_c.
19                else:
20                    min_flips += 1
21        # Return the total number of flips required
22        return min_flips
23

1class Solution {
2
3    // This method calculates the minimum number of flips required to make
4    // bitwise OR of 'a' and 'b' equal to 'c'.
5    public int minFlips(int a, int b, int c) {
6        // Initialize the variable to store the count of minimum flips.
7        int minFlipsCount = 0;
8      
9        // Iterate over each bit position from 0 to 29 (30 bits in total assuming 32-bit integers)
10        // to compare the bits in 'a', 'b', and 'c'.
11        for (int i = 0; i < 30; ++i) {
12            // Extract the i-th bit from 'a', 'b', and 'c'.
13            int bitA = (a >> i) & 1;
14            int bitB = (b >> i) & 1;
15            int bitC = (c >> i) & 1;
16          
17            // Check if the result of 'bitA | bitB' doesn't match 'bitC'.
18            if ((bitA | bitB) != bitC) {
19                // If both bits in 'a' and 'b' are 1, and 'c' is 0, we need 2 flips.
20                // Otherwise, we need just 1 flip (either from 'a' or 'b', or to match a 1 in 'c').
21                minFlipsCount += (bitA == 1 && bitB == 1) ? 2 : 1;
22            }
23        }
24      
25        // Return the total count of flips required.
26        return minFlipsCount;
27    }
28}
29

1class Solution {
2public:
3    // Method to calculate the minimum number of flips to make a | b equal to c
4    int minFlips(int a, int b, int c) {
5        int flipsCount = 0; // Variable to hold the total number of bit flips required
6
7        // Loop through each bit position (from 0 to 29)
8        for (int i = 0; i < 30; ++i) {
9            // Extract the i-th bits from a, b, and c
10            int bitA = (a >> i) & 1;
11            int bitB = (b >> i) & 1;
12            int bitC = (c >> i) & 1;
13
14            // Check if the current bits of a OR b differ from the corresponding bit of c
15            if ((bitA | bitB) != bitC) {
16                // If both bits in a and b are 1 then we need to flip both (2 flips),
17                // otherwise, we need to flip only one bit
18                flipsCount += (bitA == 1 && bitB == 1) ? 2 : 1;
19            }
20        }
21
22        // Return the total number of flips required
23        return flipsCount;
24    }
25};
26

1// Function to calculate the minimum number of flips to make a | b equal to c
2function minFlips(a: number, b: number, c: number): number {
3    let flipsCount: number = 0; // Variable to hold the total number of bit flips required
4
5    // Loop through each bit position (from 0 to 29)
6    for (let i = 0; i < 30; ++i) {
7        // Extract the i-th bits from a, b, and c
8        const bitA: number = (a >> i) & 1;
9        const bitB: number = (b >> i) & 1;
10        const bitC: number = (c >> i) & 1;
11
12        // Check if the current bits of a OR b differ from the corresponding bit of c
13        if ((bitA | bitB) !== bitC) {
14            // If both bits in a and b are 1 then we need to flip both (2 flips),
15            // otherwise, we flip only one bit
16            flipsCount += (bitA === 1 && bitB === 1) ? 2 : 1;
17        }
18    }
19
20    // Return the total number of flips required
21    return flipsCount;
22}
23

Time and Space Complexity

The time complexity of the provided code is O(1). While there is a loop that iterates up to 30 times, this is a constant factor because the size of an integer in most languages is fixed (here it's assumed to be 32 bits, and the loop runs for up to 30 significant bits). Thus, the number of iterations does not depend on the size of the input, making it constant-time complexity.

The space complexity of the code is also O(1). No additional space is used that grows with the size of the input. The variables x, y, z, and ans use a fixed amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know