Number Complement

Leetcode Problem:

• Number Complement

Summary

• This problem requires finding the complement of a given integer
• The complement is the integer that is obtained by flipping all the 0's to 1's and all the 1's to 0's in the binary representation of the given integer.

Approach

• The approach used in the solution is to use a bitmask to keep track of the bits that have been flipped
• The bitmask is initialized to 1 and is shifted left by 1 bit in each iteration
• If the current bit in the bitmask is not set in the given integer, it is added to the result
• This process continues until the bitmask is greater than or equal to the given integer.

Complexity

• The time complexity of the solution is O(log n), where n is the given integer
• This is because the while loop runs for log n iterations, where log n is the number of bits in the binary representation of the given integer.

Explain

• Here is the solution code with comments: class Solution { public: int findComplement(int num) { // Initialize the result to 0 int res = 0; // Initialize the bitmask to 1 unsigned int bitmask = 1; // Continue the loop until the bitmask is greater than or equal to the given integer while(bitmask < num){ // If the current bit in the bitmask is not set in the given integer, // add the bitmask to the result if(!(bitmask & num)){ res += bitmask; } // Shift the bitmask left by 1 bit for the next iteration bitmask <<= 1; } // Return the result return res; } };

Solution Code:

class Solution {
public:
    int findComplement(int num) {
        int res = 0;
        unsigned int bitmask = 1;
        while(bitmask < num){
            if(!(bitmask & num)){
                res += bitmask;
            }
            bitmask <<= 1;
        }
        return res;
    }
};