
Description
The problem involves finding the minimum number of bit flips required to make the bitwise OR of two integers a
and b
equal to a third integer c
. Each bit in a
, b
, and c
is examined individually, and based on the value of each bit, the number of operations required to achieve the desired outcome is calculated.
Intuition
The key insight is to recognize that for each bit position, we can determine the necessary operations by comparing the bits of a
, b
, and c
. If the bit in c
is 1
, at least one of the corresponding bits in a
or b
must be 1
. If the bit in c
is 0
, both corresponding bits in a
and b
must be 0
. The number of flips required is based on whether these conditions are met.
Approach
- Initialize a counter to track the number of operations (bit flips).
- Use a loop to iterate through each bit position of
a
,b
, andc
until all bits have been processed. - For each bit:
- If the bit in
c
is1
, check if both bits ina
andb
are0
. If so, one flip is required. - If the bit inc
is0
, check if either bit ina
orb
is1
. If so, flips are required to turn them to0
. - Shift
a
,b
, andc
right by one bit after each iteration to process the next bit. - Continue until all bits have been processed and return the total number of operations.
Complexity
Time Complexity:
O(log(max(a, b, c)))
where log(max(a, b, c))
represents the number of bits required to represent the largest number among a
, b
, and c
. Each bit is processed in constant time.
Space Complexity:
O(1)
since only a few variables are used, and no additional space is required beyond the input size.
Code
C++
class Solution {
public:
int minFlips(int a, int b, int c) {
int operations = 0;
while (a > 0 || b > 0 || c > 0) {
if (c & 1) {
if (!(a & 1 || b & 1)) {
operations++;
}
} else {
if (a & 1) {
operations++;
}
if (b & 1) {
operations++;
}
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return operations;
}
};
Python
class Solution:
def minFlips(self, a: int, b: int, c: int) -> int:
operations = 0
while a > 0 or b > 0 or c > 0:
if c & 1:
if not (a & 1 or b & 1):
operations += 1
else:
if a & 1:
operations += 1
if b & 1:
operations += 1
a >>= 1
b >>= 1
c >>= 1
return operations
Java
class Solution {
public int minFlips(int a, int b, int c) {
int operations = 0;
while (a > 0 || b > 0 || c > 0) {
if ((c & 1) == 1) {
if ((a & 1) == 0 && (b & 1) == 0) {
operations++;
}
} else {
if ((a & 1) == 1) {
operations++;
}
if ((b & 1) == 1) {
operations++;
}
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return operations;
}
}
JavaScript
var minFlips = function(a, b, c) {
let operations = 0;
while (a > 0 || b > 0 || c > 0) {
if (c & 1) {
if (!(a & 1 || b & 1)) {
operations++;
}
} else {
if (a & 1) {
operations++;
}
if (b & 1) {
operations++;
}
}
a >>= 1;
b >>= 1;
c >>= 1;
}
return operations;
};