LeetCode 504: Base 7

Problem Restatement

We are given an integer num.

We need to return its representation in base 7 as a string.

The official problem asks us to convert an integer from base 10 into base 7. Negative numbers should keep the negative sign. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def convertToBase7(self, num: int) -> str:
        ...

Examples

Example 1:

num = 100

We repeatedly divide by 7.

The remainders are:

100 % 7 = 2
14 % 7 = 0
2 % 7 = 2

Reading remainders from bottom to top gives:

202

So the answer is:

"202"

Example 2:

num = -7

The base 7 representation of 7 is:

10

Preserve the negative sign:

"-10"

First Thought: Use Repeated Division

This problem follows the standard base conversion process.

For a positive number:

1. Divide by 7.
2. Record the remainder.
3. Continue with the quotient.
4. Reverse the collected digits.

The remainder gives the next digit in base 7.

For example:

100 / 7 = 14 remainder 2
14 / 7 = 2 remainder 0
2 / 7 = 0 remainder 2

So the digits are:

2, 0, 2

Reversed:

202

Key Insight

The least significant digit of a base b representation is always:

num % b

After removing that digit:

num //= b

So repeated modulo and integer division gradually build the representation.

For this problem:

b = 7

Algorithm

Handle the special case:

num == 0

because its representation is simply:

"0"

Then:

1. Record whether the number is negative.
2. Work with the absolute value.
3. Repeatedly:
   • append num % 7
   • update num //= 7
4. Reverse the digits.
5. Add the negative sign if needed.

Correctness

At every step, the algorithm extracts:

num % 7

which is exactly the least significant base 7 digit of the current number.

Integer division:

num // 7

removes that least significant digit from further consideration.

Repeating this process eventually reduces the number to 0.

The collected digits are generated from least significant to most significant order, so reversing them produces the correct base 7 representation.

If the original number was negative, prepending "-" gives the correct signed representation.

Therefore the algorithm returns the correct base 7 string.

Complexity

The number of digits in base 7 is proportional to:

log₇ n

Implementation

class Solution:
    def convertToBase7(self, num: int) -> str:
        if num == 0:
            return "0"

        negative = num < 0
        num = abs(num)

        digits = []

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

        result = "".join(reversed(digits))

        if negative:
            result = "-" + result

        return result

Code Explanation

Handle the zero case first:

if num == 0:
    return "0"

Without this case, the loop would generate no digits.

Track whether the number was negative:

negative = num < 0

Then work with the absolute value:

num = abs(num)

The digits are stored in a list:

digits = []

Each iteration extracts one base 7 digit:

digits.append(str(num % 7))

Then remove the extracted digit:

num //= 7

The digits were generated backwards, so reverse them:

result = "".join(reversed(digits))

Finally, restore the negative sign if necessary:

if negative:
    result = "-" + result

Testing

def test_convert_to_base7():
    s = Solution()

    assert s.convertToBase7(100) == "202"
    assert s.convertToBase7(-7) == "-10"
    assert s.convertToBase7(0) == "0"
    assert s.convertToBase7(7) == "10"
    assert s.convertToBase7(49) == "100"
    assert s.convertToBase7(1) == "1"

    print("all tests passed")

Test meaning: