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