LeetCode 504 - Base 7

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

The problem asks us to convert a given integer num into its representation in base 7, returning the result as a string. In other words, instead of representing the number in the usual decimal system (base 10), we represent it in a numeral system where each digit represents a power of 7, ranging from 0 to 6. For example, the decimal number 100 becomes "202" in base 7 because 2×7² + 0×7¹ + 2×7⁰ = 100.

The input num can be positive, negative, or zero. The output must be a string, and if the number is negative, the string should start with a minus sign. The constraints, -10^7 <= num <= 10^7, indicate that the input values are moderate and will not cause integer overflow in most programming languages.

Important edge cases include zero, negative numbers, and numbers that are exactly a power of 7, as these could lead to incorrect handling if the conversion logic does not account for sign or digit calculation properly. The problem guarantees that num is always an integer within the specified bounds.

Approaches

A brute-force approach to this problem would involve repeatedly subtracting powers of 7 to build the base 7 representation. You would start from the largest power of 7 smaller than the number and find the coefficient for each power, appending it to a string. This method works but is unnecessarily complicated and inefficient because it requires repeatedly calculating powers of 7 and handling each coefficient manually.

The optimal approach relies on the standard base conversion technique: repeatedly divide the number by 7 and store the remainders. This works because in any positional numeral system, dividing by the base gives the next higher digit in the representation. By collecting remainders and reversing them at the end, we obtain the correct base 7 string. We must handle negative numbers carefully by converting their absolute value first and then prepending a minus sign if necessary.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log(num)²)	O(log(num))	Uses repeated subtraction and power calculations, correct but cumbersome
Optimal	O(log(num))	O(log(num))	Standard division-remainder method, handles negative numbers easily

Algorithm Walkthrough

Check if the input num is zero. If it is, return the string "0" immediately because zero is the same in any base.
Determine the sign of the number. If num is negative, note this and work with its absolute value to simplify the conversion process.
Initialize an empty list or string to store the digits of the base 7 number.
While the number is greater than zero, perform the following steps:
Divide the number by 7 and record the remainder.
Append the remainder to the digits collection. This remainder represents the least significant digit in base 7 at this stage.
Update the number by integer-dividing it by 7 to remove the digit just processed.
After the loop, reverse the digits collection because the remainders were generated from least significant to most significant.
If the original number was negative, prepend a minus sign to the resulting string.
Return the resulting string.

Why it works: Each iteration of dividing by 7 produces the next least significant digit in base 7. Collecting these digits and reversing them reconstructs the correct number in base 7. Handling the absolute value ensures that the negative sign does not interfere with digit calculation.

Python Solution

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
        
        base7 = "".join(reversed(digits))
        if negative:
            base7 = "-" + base7
        
        return base7

In this implementation, we first handle the zero case. We then determine whether the input is negative and work with the absolute value. The while loop repeatedly extracts the least significant digit by taking the remainder modulo 7, appending it as a string, and reducing num by integer division. After collecting all digits, we reverse them and prepend a minus sign if needed.

Go Solution

import "strconv"

func convertToBase7(num int) string {
    if num == 0 {
        return "0"
    }

    negative := num < 0
    if negative {
        num = -num
    }

    digits := []byte{}
    for num > 0 {
        remainder := num % 7
        digits = append(digits, byte(remainder)+'0')
        num /= 7
    }

    // Reverse digits
    for i, j := 0, len(digits)-1; i < j; i, j = i+1, j-1 {
        digits[i], digits[j] = digits[j], digits[i]
    }

    if negative {
        return "-" + string(digits)
    }
    return string(digits)
}

In Go, we use a []byte slice to store digits because it is more efficient than building strings incrementally. We convert each remainder to a byte character by adding '0'. After reversing the slice, we handle the negative sign by concatenating a "-" if necessary. Go requires explicit type conversions between integers and bytes when building strings.

Worked Examples

Example 1: num = 100

Step	num	num % 7	digits
Initial	100	-	[]
1	100	2	['2']
2	14	0	['2', '0']
3	2	2	['2', '0', '2']

Reverse digits: '202'

Example 2: num = -7

Step	num	num % 7	digits
Initial	7	-	[]
1	7	0	['0']
2	1	1	['0', '1']

Reverse digits and prepend '-': '-10'

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log7(num))	Each division reduces the number by a factor of 7, giving logarithmic steps
Space	O(log7(num))	Space required to store the digits, which is proportional to the number of digits in base 7

The algorithm is efficient because it reduces the number by a factor of 7 in each iteration, resulting in a logarithmic number of steps relative to the input value. Space usage is minimal, only proportional to the length of the resulting base 7 string.

Test Cases

# Provided examples
assert Solution().convertToBase7(100) == "202"  # positive number
assert Solution().convertToBase7(-7) == "-10"  # negative number

# Boundary cases
assert Solution().convertToBase7(0) == "0"     # zero input
assert Solution().convertToBase7(1) == "1"     # smallest positive number
assert Solution().convertToBase7(-1) == "-1"   # smallest negative number
assert Solution().convertToBase7(7) == "10"    # power of 7
assert Solution().convertToBase7(-343) == "-1000"  # negative power of 7

# Stress cases
assert Solution().convertToBase7(10000000) == "104134211"  # large positive
assert Solution().convertToBase7(-10000000) == "-104134211" # large negative

Test	Why
100	typical positive number
-7	negative number handling
0	zero edge case
1, -1	smallest absolute values
7, -343	exact powers of 7
10000000, -10000000	stress test with largest input magnitude

Edge Cases

A common edge case is zero. Since the standard algorithm relies on dividing by 7, a naive loop would skip zero entirely. We handle this explicitly by returning "0".

Negative numbers are another edge case. If we apply the division and remainder steps directly on a negative number, we may produce incorrect digits. We handle this by converting to the absolute value first, then prepending a minus sign after processing.

Numbers that are exact powers of 7, like 7, 49, or 343, can expose off-by-one errors. Without careful handling, one could miscalculate the highest-order digit. Our algorithm correctly appends all digits and reverses them, producing the expected representation.