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 (aORb==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^91 <= b <= 10^91 <= c <= 10^9The key idea in #1318 Minimum Flips to Make a OR b Equal to c is to analyze how the OR operation behaves at the bit level. Since the OR of two bits determines whether the resulting bit is 1 or 0, we can inspect each bit of a, b, and c independently.
Iterate through the binary representation of the numbers (usually up to 31 or 32 bits). For each position, check the current bits of a, b, and c. If the OR result already matches the corresponding bit in c, no action is required. Otherwise, calculate the minimum number of flips needed to adjust either a or b so that the OR result becomes correct.
Bit manipulation techniques such as bit masking, bit shifting, or directly checking bits using & can help process each position efficiently. Because each bit is processed once, the approach runs in constant time relative to integer size.
Time Complexity: O(1) since integers have a fixed number of bits.
Space Complexity: O(1) as only a few variables are used.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Bit-by-bit comparison using bit manipulation | O(1) | O(1) |
codestorywithMIK
Use these hints if you're stuck. Try solving on your own first.
Check the bits one by one whether they need to be flipped.
The key to this approach is analyzing each bit position of the numbers. We need to ensure that at each bit position i, (a[i] OR b[i]) matches c[i].
If c[i] is 0, both a[i] and b[i] must be 0. This may require flipping if either a[i] or b[i] is 1.
If c[i] is 1, we need at least one of a[i] or b[i] to be 1. If both are 0, we need one flip.
By iterating through each binary bit, we can count the necessary flips.
Time Complexity: O(1), since the number of bits is constant and we iterate a fixed number of times.
Space Complexity: O(1), as we use a constant amount of space.
1#include <stdio.h>
2
3int minFlips(int a, int b, int c) {
4 int flips = 0
The function minFlips calculates the number of flips required to make (a OR b) equal to c. The code iterates through 32 bits (considering an integer size of 32) and uses bitwise operations to check each individual bit position of a, b, and c.
This alternative approach uses masks and logical reduction to simplify determining the minimum flips. Instead of checking each bit individually, create a mask that highlights the bits where a OR b does not match the bits of c.
For c's zeroed bits, count additions for every 1 found in corresponding bits in a or b.
For c's one bits, ensure at least one 1 is present in the corresponding a or b position. Adjust flips accordingly.
Time Complexity: O(1), consistently iterating fixed bits.
Space Complexity: O(1), as it uses primitive operations.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Bit manipulation allows you to directly inspect how each bit contributes to the OR operation. Since OR works independently per bit, analyzing each position lets you compute the exact number of flips required without modifying the entire number.
Yes, variations of bit manipulation problems like this are common in technical interviews at companies such as Amazon, Google, and Meta. They test understanding of bitwise operations, logical reasoning, and the ability to optimize solutions using low-level operations.
No complex data structure is required for this problem. Bitwise operations on integers are sufficient, making the solution efficient and straightforward. Using bit masks and shifts allows you to inspect and modify individual bits easily.
The optimal approach is to analyze each bit of a, b, and c independently using bit manipulation. For every bit position, determine whether the OR result matches the target bit in c and count the minimum flips required. Since integers have a fixed number of bits, the algorithm runs in constant time.
JavaScript follows a strategy of iterative bit examination and reduction through while loops, ensuring each loop evaluates a fixed number of positions for consistent flip calculation.