Complement of Base 10 Integer

Difficulty: Easy | Acceptance: 63.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 n, return its complement.

• Examples
• Constraints
• Bit Manipulation with Mask
• Bit Shifting
• String Conversion

Examples

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

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints

0 <= num <= 10^9

Bit Manipulation with Mask

Intuition To find the complement, we can XOR the number n with a mask that has all bits set to 1 up to the most significant bit (MSB) of n. XORing a bit with 1 flips it.

Steps

• Handle the edge case where n is 0 (return 1).
• Calculate the number of bits required to represent n.
• Create a mask by shifting 1 left by the bit count and subtracting 1 (e.g., for 3 bits, 1 << 3 is 1000, minus 1 is 111).
• Return n ^ mask.

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        mask = (1 << n.bit_length()) - 1
        return n ^ mask

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the most efficient approach using built-in bit functions.

Bit Shifting

Intuition We can build the mask bit by bit. We iterate through the bits of n, shifting the mask left and adding 1 until we have processed all bits of n.

Steps

• If n is 0, return 1.
• Initialize mask to 0 and temp to n.
• While temp is greater than 0, shift mask left by 1, OR it with 1, and shift temp right by 1.
• Finally, return n ^ mask.

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

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Iterates once per bit of the number.

String Conversion

Intuition Convert the integer to its binary string representation, iterate through the string to flip the bits, and then convert the result back to an integer.

Steps

• If n is 0, return 1.
• Convert n to a binary string.
• Create a new string by flipping ‘0’ to ‘1’ and ‘1’ to ‘0’.
• Parse the new binary string back to an integer.

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        if n == 0:
            return 1
        binary = bin(n)[2:]
        complement = ""
        for bit in binary:
            if bit == "0":
                complement += "1"
            else:
                complement += "0"
        return int(complement, 2)

Complexity

• Time: O(log n)
• Space: O(log n)
• Notes: Less efficient due to string manipulation overhead.