Sponsored
Sponsored
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.
1def minFlips(a: int, b: int, c: int) -> int:
2 flips = 0
3 for i in range(32):
4 bitA = (a >> i) & 1
5 bitB = (b >> i) & 1
6 bitC = (c >> i) & 1
7 if bitC == 0:
8 flips += bitA + bitB
9 else:
10 if bitA == 0 and bitB == 0:
11 flips += 1
12 return flips
13
14print(minFlips(2, 6, 5))In Python, the function iterates through the 32 possible bit positions and evaluates the states of bits from a, b, and c. It accumulates the count of flips needed where (a OR b) does not match 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.
The Python version simplifies using while-loops ensuring active bits in any of the variables. Flips are incrementally accumulated through logical deductions.