Code Implementation

class Solution:
    def findComplement(self, num: int) -> int:
        if num == 0:
            return 1
        mask = 0
        temp = num
        while temp:
            mask = (mask << 1) | 1
            temp >>= 1
        return num ^ mask
      

class Solution {
public:
    int findComplement(int num) {
        if (num == 0) return 1;
        int mask = 0, temp = num;
        while (temp) {
            mask = (mask << 1) | 1;
            temp >>= 1;
        }
        return num ^ mask;
    }
};
      

class Solution {
    public int findComplement(int num) {
        if (num == 0) return 1;
        int mask = 0, temp = num;
        while (temp != 0) {
            mask = (mask << 1) | 1;
            temp >>= 1;
        }
        return num ^ mask;
    }
}
      

var findComplement = function(num) {
    if (num === 0) return 1;
    let mask = 0, temp = num;
    while (temp) {
        mask = (mask << 1) | 1;
        temp >>= 1;
    }
    return num ^ mask;
};
      

Problem Description

The Number Complement problem asks you to find the complement of a given positive integer num. The complement of a number is defined as flipping all the bits in its binary representation (i.e., changing all 0s to 1s and all 1s to 0s), but only for the bits that are present in the original number (ignoring leading zeros).

For example, if num = 5 (which is 101 in binary), its complement is 010 in binary, which is 2 in decimal.

• Input: A single integer num (guaranteed to be non-negative).
• Output: The complement of num as an integer.
• Constraints: The solution should only flip bits up to the most significant bit of num (no leading zeros).

Thought Process

At first glance, you might think of converting the number to binary, flipping each bit, and then converting it back to decimal. While this works, it can be inefficient, especially if you use string manipulation.

A more optimized approach is to work directly with bits. The key observation is that you only need to flip the bits that are present in the number (that is, up to the most significant 1 in the binary representation). Any bits beyond that are just leading zeros and should not be flipped.

The challenge is to create a "mask" that has 1s in all the positions where num has bits, and 0s elsewhere. Then, using the XOR operation, you can flip just those bits.

Solution Approach

• Step 1: Handle Edge Case
  • If num is 0, its complement should be 1 (since 0 in binary is 0, and flipping gives 1).
• Step 2: Build the Mask
  • Initialize mask to 0 and temp to num.
  • While temp is not zero, shift mask left by 1 and set the least significant bit to 1 (i.e., mask = (mask << 1) | 1).
  • Shift temp right by 1 each time to count the number of bits in num.
  • At the end, mask will have all 1s in the positions where num has bits.
• Step 3: XOR to Flip Bits
  • Return num ^ mask. This will flip all the bits in num up to its most significant 1.

This approach avoids converting to strings and leverages bitwise operations for efficiency.

Example Walkthrough

Let's walk through the process with num = 5:

• Step 1: num = 5 in binary is 101.
• Step 2: Build the mask:
  • First loop: mask = 1 (binary 1), temp = 2
  • Second loop: mask = 3 (binary 11), temp = 1
  • Third loop: mask = 7 (binary 111), temp = 0
  • Now temp is 0, so mask is 111 in binary (decimal 7).
• Step 3: XOR num with mask:
  • 5 ^ 7 = 101 ^ 111 = 010 (binary), which is 2 in decimal.
• Result: The complement of 5 is 2.

Time and Space Complexity

• Brute-force Approach:
  • Convert number to binary string, flip bits, convert back to integer.
  • Time Complexity: O(N), where N is the number of bits in num.
  • Space Complexity: O(N), since you store the string representation.
• Optimized Bitwise Approach (this solution):
  • Time Complexity: O(1) in practice, as integer size is fixed (e.g., 32 bits), but theoretically O(N) for N bits.
  • Space Complexity: O(1), as only a few integer variables are used.
  • This is much more efficient, especially for large numbers.

Summary

The Number Complement problem is elegantly solved with bitwise operations. By constructing a mask of 1s that matches the length of the original number's binary representation, and then XORing the number with this mask, you efficiently flip only the relevant bits. This avoids unnecessary string manipulation and leverages the power of bitwise math, making the solution both fast and concise.