Base 7

Difficulty: Easy | Acceptance: 54.50% | Paid: No Topics: Math, String

Given an integer num, return a string representing its base 7 representation.

Examples

Input: num = 100
Output: "202"
Explanation: 202 in base 7 is 2*7² + 0*7 + 2 = 98 + 0 + 2 = 100.

Input: num = -7
Output: "-10"

Constraints

-10⁷ <= num <= 10⁷

• Iterative Division
• Recursive Conversion

Iterative Division

Intuition To convert a decimal number to base 7, we repeatedly divide the number by 7 and record the remainders. The remainders, read in reverse order, form the base 7 representation.

Steps

• Handle the edge case where num is 0 by returning “0”.
• Determine if the number is negative and store the sign. Work with the absolute value of the number.
• Use a loop to repeatedly divide the number by 7.
• In each iteration, calculate the remainder (num % 7) and prepend it to the result string (or append and reverse later).
• Update the number by performing integer division (num // 7).
• If the original number was negative, prepend a ”-” sign to the result.

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return "0"
        
        negative = num < 0
        num = abs(num)
        res = []
        
        while num > 0:
            res.append(str(num % 7))
            num //= 7
        
        if negative:
            res.append("-")
            
        return "".join(reversed(res))

Complexity

• Time: O(log₇ n)
• Space: O(log₇ n)
• Notes: The time complexity is logarithmic because we divide the number by 7 in each step. The space complexity is due to storing the result string.

Recursive Conversion

Intuition Base conversion can be naturally expressed recursively. The base 7 representation of a number n is the base 7 representation of n / 7 followed by the digit n % 7.

Steps

• Handle the base case: if the absolute value of num is less than 7, return its string representation.
• If the number is negative, return ”-” concatenated with the result of the recursive call on the positive value.
• Otherwise, recursively call the function on num / 7 and concatenate the result with num % 7.

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num < 0:
            return "-" + self.convertToBase7(-num)
        if num < 7:
            return str(num)
        return self.convertToBase7(num // 7) + str(num % 7)

Complexity

• Time: O(log₇ n)
• Space: O(log₇ n)
• Notes: The space complexity includes the stack space used by the recursion, which is proportional to the number of digits.