Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Different base-k number systems

We’ve currently worked with regular base-10 numbers (combinations of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) and base-2 binary numbers (0s and 1s). We’ve seen how to convert numbers from binary (base-2) to base-10 and back.
There are many other number systems. Some of the more popular ones include base-8 (octal) and base-16 (hexadecimal) systems. It’s possible to convert numbers from any of those systems to any of the other ones.
We can apply the same technique of “shifting” the number’s last digit and taking the remainder to convert from base-k to base-10:
``````k = 8       # octal number system

# base-k and base-10 numbers
bk, n = [2, 1, 4, 5, 6, 1], 0
base = 1

for ai in bk[::-1]:
n += ai * base
base *= k

print(n)``````
``````k = 8       # octal number system

# base-k and base-10 numbers
bk, n = [], 5234

while n > 0:
bk.append(n % k)
n //= k

print(bk[::-1])``````

Here when converting from a base-k to a decimal notation, we iterate over all the “digits” in the base-k number and add those to the resulting decimal number `n` on each iteration. We loop from the least significant digit to the most significant one. On each iteration, we update the base of the current iteration (1, 8, 64, 512, … for base-8) (1, 2, 4, 8, 16, 32, … for base-2) to multiply that by the digit in the base-k system. So, the least significant digit is multiplied by `1`, the next one is multiplied by `k`, the next one by `k*k`, etc.
When converting from decimal to a base-k system, we iterate from the least significant digit in the decimal notation (the last digit of an integer) and calculate the remainder of that number when divided by `k`. This gives us the least significant “digit” in the base-k system of the corresponding number. We then divide the initial number `n` by `k`, which “shifts” the number by one digit in the base-k system. We repeat the same process to obtain the next least significant “digit”. This process is repeated until the number `n` is 0 - meaning there are no digits left to process.
Note that we keep the `bk` numbers in an array to make sure this approach works for any kind of base `k`. The number `k` can be larger than 10 - like 16 which would make it impossible to store the base-k number as an integer, which only supports digits from 0 to 9. If the base is smaller than 10, we can keep the resulting digits in the base `k` system as an integer.

### Challenge

Given an integer `n` in a base-10 number system, you are asked to convert it to a base-3 system.

#### Input

The only line of the input contains a single integer `n` (0 ≤ n ≤ ).

#### Output

The output should contain the base-3 representation of `n`.

#### Examples

 Input Output 3 10 2 2

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB