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 < 109

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 log2N.

    Leave a Reply

    Your email address will not be published. Required fields are marked *