Base 7 - Solution & Explanation

Problem Overview: Given an integer num, return its representation in base 7 as a string. The task is essentially base conversion: repeatedly divide the number by 7 and collect the remainders that form the digits of the base‑7 number.

Approach 1: Iterative Division Approach (O(log₇ n) time, O(log₇ n) space)

The standard base conversion technique repeatedly divides the number by the target base and records the remainder. Start with num, compute num % 7 to get the least significant base‑7 digit, then update num = num // 7. Continue until the number becomes zero. Because digits are produced from least significant to most significant, append them to a buffer and reverse at the end (or prepend each digit). Handle negative numbers by storing the sign and converting the absolute value first. This approach runs in O(log₇ n) time because each division reduces the number by a factor of 7, and it uses O(log₇ n) space for the resulting string. The logic relies purely on arithmetic operations from math, making it simple and efficient.

Approach 2: Recursive Division Approach (O(log₇ n) time, O(log₇ n) space)

The same division idea can be expressed recursively. Instead of building digits iteratively, recursively process num // 7 until the base case (num < 7) is reached. Each recursive call returns the base‑7 representation of the higher digits, and the current remainder num % 7 is appended to the result. The recursion depth equals the number of base‑7 digits, which is O(log₇ n). Space complexity is also O(log₇ n) due to the call stack. This style highlights the natural decomposition of the number into higher digits and the current digit, a common pattern in recursion problems involving numeric representation.

Both approaches rely on the same mathematical insight: any number in base 10 can be represented as repeated divisions by the new base, collecting remainders as digits. The iterative version builds the result explicitly with a loop, while the recursive version constructs it during the return phase of function calls.

Recommended for interviews: The iterative division approach is typically expected. It demonstrates that you understand base conversion mechanics and can implement it efficiently using simple arithmetic operations. The recursive approach is clean and expressive but adds call‑stack overhead, so it’s better presented as an alternative after explaining the iterative method. Showing both reinforces your understanding of number representation and basic math transformations.