fb pixel

Algorithms and Data Structures

  • Profound Academy

    • 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

  • 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)
    base-k → base-10 conversion
    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])
    base-10 → base-k conversion
     
    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
     
    To check your solution you need to sign in
    Sign in to continue