Dare2Solve
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.
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.
a
, b
, and c
until all bits have been processed.c
is 1
, check if both bits in a
and b
are 0
. If so, one flip is required.c
is 0
, check if either bit in a
or b
is 1
. If so, flips are required to turn them to 0
.a
, b
, and c
right by one bit after each iteration to process the next bit.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.
O(1)
since only a few variables are used, and no additional space is required beyond the input size.
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;
}
};
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
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;
}
}
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;
};