Complement of Base 10 Integer | LeetCode | Solution Explained

LeetCode 1009. Complement of Base 10 Integer. I explain the solution in Python3 using multiple implementations. Problem Link.

0. Complement of Base 10 Integer: Problem Discussion

0.0. IO Format

• input: n input number in base 10
• output: complement of n
• constraint:
  • 0 <= n < 10⁹

0.1. Examples

• n = 5 –> “101” –> “010” –> 2 = output
• n = 4 –> “100” –> “011” –> 3 = output

1. Complement of Base 10 Integer: Observations & Logic

1.0. Intuitions

Let’s follow exactly as what the question says:

• take the input n
• convert the integer to its binary representation
• flip the bits in binary representation
• convert the binary representation to integer (base 10) representation again

2. Complement of Base 10 Integer: Implementation

2.0. Code: Built In Functions

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

2.1. Code: Manual Functions

class Solution:
    def bitwiseComplement(self, n: int) -> int:
        def int_to_base(num, base):
            x = ""
            while num:
                x = str(num % base) + x
                num = num // base
            return x if x else "0"
        
        def base_to_int(s, base):
            num = 0
            for c in s:
                num = base * num + int(c)
            return num

        x = ""
        for c in int_to_base(n, 2): 
            if c == "0": x += "1"
            else: x += "0"
        
        return base_to_int(x, 2)

2.2. Complexity Analysis

• Time: O(log2N)
• Space: O(log2N)

Same space time complexity since we have to convert the input to an intermediate binary representation, of the size log₂N.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.