Leetcode – Base 7 Solution in Python

Spread the love

Introduction

In this article, we will extensively dissect the Base 7 problem on Leetcode and explore different approaches to solve it using Python.

The Base 7 problem is as follows:

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

For example.

Input: 100
Output: "202"

Input: -7
Output: "-10"

Approach 1: The Basic Algorithm

This approach involves converting the given integer into base 7 through a series of divisions and concatenating remainders. Since 7 is the base, we repeatedly divide the number by 7 and accumulate the remainders in reverse order.

Here is the Python code that demonstrates this approach.

def convertToBase7(num):
    if num == 0:
        return "0"
    
    result = []
    is_negative = num < 0
    num = abs(num)
    
    while num > 0:
        result.append(str(num % 7))
        num //= 7
    
    # Reverse and join the digits
    result = result[::-1]
    
    # Add negative sign if necessary
    return '-' + ''.join(result) if is_negative else ''.join(result)

This approach is simple and has a time complexity of O(log(num)) since we divide the number by 7 in each iteration.

Approach 2: Using Python’s Built-in Functions

Python offers built-in functions that allow us to easily convert numbers from one base to another. By using Python’s in-built divmod() function, we can get both the quotient and remainder simultaneously, which can slightly optimize our basic algorithm.

def convertToBase7(num):
    if num == 0:
        return "0"
    
    result = []
    is_negative = num < 0
    num = abs(num)
    
    while num > 0:
        num, remainder = divmod(num, 7)
        result.append(str(remainder))
    
    # Reverse and join the digits
    result = result[::-1]
    
    # Add negative sign if necessary
    return '-' + ''.join(result) if is_negative else ''.join(result)

Approach 3: Recursive Solution

We can solve this problem using recursion as well. We can recursively process the number, divide it by 7, and concatenate the remainders.

Here’s how we can do it.

def convertToBase7(num):
    # Handling the base case of 0
    if num == 0:
        return "0"
    
    # Recursive function to find the base 7 representation
    def recursive_base7(n):
        if n == 0:
            return ''
        n, remainder = divmod(abs(n), 7)
        return recursive_base7(n) + str(remainder)
    
    # Add a negative sign if necessary
    return '-' + recursive_base7(num) if num < 0 else recursive_base7(num)

This recursive approach is elegant but might cause stack overflow for very large inputs.

Approach 4: Using String Formatting

Python has powerful string formatting capabilities. We can actually utilize this to convert a number to any base between 2 and 36 inclusive, by employing the format function.

def convertToBase7(num):
    # Using string formatting to convert to base 7
    # Note that this approach is limited to bases between 2 and 36
    return format(num, '#0d').replace("0", "").replace("x","").replace("b", "")

This approach might look magical, but it leverages Python’s string formatting capabilities to do the heavy lifting.

Conclusion

In this article, we examined the Base 7 problem on Leetcode and discussed various approaches to solve it in Python. We started with the basic algorithm and then enhanced it using Python’s built-in functions. We also explored a recursive solution and ultimately observed how Python’s powerful string formatting can be leveraged for base conversions.

Leave a Reply