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
non 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
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
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
nis 0 - meaning there are no digits left to process.
Note that we keep the
bknumbers in an array to make sure this approach works for any kind of base
k. The number
kcan 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
ksystem as an integer.
Given an integer
nin a base-10 number system, you are asked to convert it to a base-3 system.
The only line of the input contains a single integer
n(0 ≤ n ≤ ).
The output should contain the base-3 representation of