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

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

### Recommended Posts

##### Majority Element | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.