Approach
Continuing the coding challenge, I thought I'd give a medium a try on Leetcode.
The ask is to determine how many bit flips would be required to make A OR B = C.
Two pivotal pieces when solving this:
num % 2 will get the least significant bit of a positive integer
num /= 2 will remove the least significant bit of a positive integer (equivalent of logical bitshift right)
Before diving in, a small piece of critism for this question -- it does not make clear that c is not guaranteed to be the largest number, although the examples would have you believe that. This is why the first 3 lines are required, to determine which integer is largest to determine our loop constraints.
Now, I start with setting up a while-loop on the condition largest > 0. I am going to modify the arguments directly (in place) so we will divide by 2 on each iteration.
Next, I decided to store the abit, bbit, and cbit in separate variables as they will be referenced repeatedly inside the loop.
This part is no longer in the comments in the code, but I wrote out the possible combinations of abit, bbit, and cbit that would require a flip. For example:
abit == 0 bbit == 0 cbit == 1 (1 flip)
abit == 1 bbit == 1 cbit == 0 (2 flips)
abit == 0 bbit == 1 cbit == 0 (1 flip)
abit == 1 bbit == 0 cbit == 0 (1 flip)
From here, this was added into an if-else code block followed by dividing each number including largest by 2 on each iteration.
According to Leetcode, this solution beats 100% of submissions using C++ at 0ms runtime and 79.82% of users for memory usage.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Code
class Solution {
public:
int minFlips(int a, int b, int c) {
int largest = a;
if(b > largest) largest = b;
if(c > largest) largest = c;
int count = 0;
while(largest > 0){
int abit = a % 2;
int bbit = b % 2;
int cbit = c % 2;
if(abit == 0 && bbit == 0 && cbit == 1){
count++;
} else if (abit == 1 && bbit == 1 && cbit == 0){
count += 2;
} else if ((abit || bbit) != cbit){
count++;
}
a /= 2;
b /= 2;
c /= 2;
largest /= 2;
}
return count;
}
};