# 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
^{9}

- 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(log`

_{2}N) - Space:
`O(`

`log`

)_{2}N

Same space time complexity since we have to convert the input to an intermediate binary representation, of the size log_{2}N.

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