476. Number Complement

The complement of an integer is the integer you get when you flip all the 0‘s to 1‘s and all the 1‘s to 0‘s in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

Example 1:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints:

• 1 <= num < 231

Approach 01:

class Solution {
public:
    int findComplement(long num) {
        for (long i = 1; i <= num; i <<= 1)
            num ^= i;
        return num;
    }
};

class Solution:
    def findComplement(self, num: int) -> int:
        i = 1
        while i <= num:
            num ^= i
            i <<= 1
        return num

Time Complexity

• Bitwise Operations:

  The loop iterates over the bits of the number. The number of iterations is proportional to the number of bits in the binary representation of num, which is \( O(\log \text{num}) \).

• Overall Time Complexity:

  The overall time complexity is \( O(\log \text{num}) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a constant amount of extra space, regardless of the input size.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \).