504. Base 7

At first glance, Base 7 looks like a trivial number conversion task. In interviews, however, it is often used to assess whether candidates understand positional number systems, remainder-based decomposition, and edge-case handling especially around negative numbers and zero without relying on built-in shortcuts.

Problem statement

You are given an integer num. Your task is to return its base 7 representation as a string.

Constraints:

• −10⁷ <= num <= 10⁷

Examples

Intuition

Every positional number system follows the same principle.

The key insight is that the remainder after dividing by 7 gives the next digit, while integer division by 7 removes the least significant digit. Because of this, digits are produced from right to left.

Once this mental model is clear, the implementation becomes straightforward.

Base conversion using repeated division

For this problem, we can use the standard base conversion algorithm, commonly known as the repeated division (division–remainder) method.

Theis algorithm works by repeatedly dividing the number by the target base and recording the remainders. Each remainder corresponds to a digit in the new base, starting from the least significant digit. The process continues until the number is reduced to zero.

This method is canonical, efficient, and applies uniformly to conversions into any base. The only adjustment needed is to reverse the collected digits at the end, since they are generated in reverse order.

Step-by-step algorithm

1. If num == 0, return "0" immediately.
2. Record whether the number is negative.
3. Convert num to its absolute value.
4. Initialize an empty list digits to store digits.
5. While num > 0:
   1. Append num % 7 to the list.
   2. Update num = num // 7.
6. Reverse the digit list and join it into a string.
7. Add a '-' sign if the original number was negative.

Let’s look at the following illustration to get a better understanding of the solution:

1 / 4

Code implementation

Let’s look at the code for this solution below:

def convertToBase7(num):
    # Handle the special case where num is zero
    if num == 0:
        return "0"

    # Track whether the number is negative
    is_negative = num < 0
    num = abs(num)

    digits = []

    # Repeated division by 7
    while num > 0:
        digits.append(str(num % 7))
        num //= 7

    # Reverse to get correct order
    base7 = "".join(reversed(digits))

    return "-" + base7 if is_negative else base7


def main():
    testCases = [100, -7, 0, 49, -343]

    for i, num in enumerate(testCases, 1):
        print(i, ".\t Input: ", num, sep="")
        print("\t Base 7: ", convertToBase7(num), sep="")
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity

Each division by 7 removes one base-7 digit. The number of iterations is proportional to the number of digits in the base-7 representation. So, the overall time complexity of this algorithm is O(log₇ n).

Space complexity

We store one character per base-7 digit, so the overall the space complexity will be O(log₇ n).

Common pitfalls and interview tips

1. Forgetting the zero case
   If num == 0, the loop never runs. Always handle this upfront.
2. Incorrect handling of negative numbers
   Convert the number to positive first, then reapply the sign at the end.
3. Reversing logic mistakes
   Remainders are generated in reverse order. Forgetting to reverse is a common bug.
4. Using built-in base conversion directly
   Interviewers expect you to demonstrate the logic, not rely on language shortcuts.