Number Complement

Difficulty: Easy | Acceptance: 70.40% | Paid: No Topics: Bit Manipulation

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, its complement is “010” which is the integer 2.

Given an integer num, return its complement.

• Examples
• Constraints
• Bit Manipulation with Mask
• Bit by Bit Construction
• String Manipulation
• Mathematical Approach

Examples

Input: num = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Input: num = 1
Output: 0
Explanation: 1 is "1" in binary, with complement "0" in binary, which is 0 in base-10.

Constraints

1 <= num < 2^31

Bit Manipulation with Mask

Intuition Create a mask with all 1s from the most significant bit of num to the least significant bit, then XOR with num to flip only those bits.

Steps

• Find the position of the most significant bit of num
• Create a mask with all 1s from MSB to LSB
• XOR num with the mask to get the complement

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

Complexity

• Time: O(log n) - we iterate through each bit position
• Space: O(1) - only using constant extra space
• Notes: Efficient bit manipulation approach

Bit by Bit Construction

Intuition Build the complement bit by bit by iterating through each bit position and flipping the bit.

Steps

• Initialize result to 0
• Iterate through each bit position
• For each position, check if the bit is 0 or 1
• Add the flipped bit to the result

class Solution:
    def findComplement(self, num: int) -> int:
        result = 0
        bit = 0
        while num > 0:
            if num & 1 == 0:
                result |= 1 << bit
            num >>= 1
            bit += 1
        return result

Complexity

• Time: O(log n) - we iterate through each bit position
• Space: O(1) - only using constant extra space
• Notes: Straightforward but slightly more verbose than mask approach

String Manipulation

Intuition Convert the number to binary string, flip all bits, and convert back to integer.

Steps

• Convert num to binary string
• Flip each bit (0 to 1, 1 to 0)
• Convert the flipped binary string back to integer

class Solution:
    def findComplement(self, num: int) -> int:
        binary = bin(num)[2:]
        complement = ''.join('1' if b == '0' else '0' for b in binary)
        return int(complement, 2)

Complexity

• Time: O(log n) - converting to binary and processing each bit
• Space: O(log n) - storing the binary string
• Notes: Less efficient due to string operations but more readable

Mathematical Approach

Intuition The complement of num is equal to (2ᵏ - 1) - num, where k is the number of bits in num.

Steps

• Find the smallest power of 2 greater than num
• Subtract 1 to get a mask of all 1s
• Subtract num from this mask to get the complement

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

Complexity

• Time: O(log n) - finding the next power of 2
• Space: O(1) - only using constant extra space
• Notes: Mathematically elegant, equivalent to the mask approach