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 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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
The C function uses bitwise operations to derive a differential mask of bits that need checking. It iteratively reduces a, b, and c by shifting and adjusts flips by analyzing each bit state.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1), consistently iterating fixed bits.
Space Complexity: O(1), as it uses primitive operations.
| Approach | Complexity |
|---|---|
| Bit Manipulation by Checking Each Bit | Time Complexity: O(1), since the number of bits is constant and we iterate a fixed number of times. |
| Using Mask and Logical Reduction | Time Complexity: O(1), consistently iterating fixed bits. |
Minimum Flips to Make a OR b Equal to c | 2 Approaches | Microsoft | Leetcode-1318 | Explanation • codestorywithMIK • 18,156 views views
Watch 9 more video solutions →Practice Minimum Flips to Make a OR b Equal to c with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor