504_Base 7

Given an integer, return its base 7 string representation. The integer may be negative.

Example 1:

Input: 100

Output: "202"

Example 2:

Input: -7

Output: "-10"

Solution:

Idea:

• Use a sequence of module and division operations.

• The integer mod base 7 will be in the number in last digit, the integer divide base 7 is the next integer to run

• record the sign at the beginning

Time Complexity: $O(log_{7}n)$ where 7 is the base, n is the input number

Space Complexity: $O(log_{7}n)$ where 7 is the base, n is the input number

Code 1: iterative approach

def convertToBase7(num):
    """
    :type num: int
    :rtype: str
    """
    if num == 0: return "0"

    sign = "-" if num < 0 else ""
    num = abs(num)           
    output = []

    while num > 0:
        output.append(num % 7) 
        num //= 7

    return sign + "".join([str(i) for i in output[::-1]])

Code 2: recursive approach

def convertToBase7(num):
    """
    :type num: int
    :rtype: str
    """
    if abs(num) < 7: return str(num)

    sign = "-" if num < 0 else ""
    num = abs(num)

    return sign + convertToBase7(num//7) + str(num%7)