Base 13 Conversion Capital One Python Interview Question

Given an integer , return its string representation in base 13.

In case you don’t use base 13 that much (who does, right?), here’s a quick rundown: just like base 10 uses digits from 0 to 9. But also for 10, 11 and 12, we use the letters A, B, and C.

For example:

• 9 in base 13 is still
• 10 in base 13 is
• 11 in base 13 is
• 12 in base 13 is
• 13 in base 13 is
• 14 in base 13 is
• 49 in base 13 is (since $3*13 + 10 = 49$)
• 69 in base 13 is (since $5*13 + 4 = 69$)

Iterative Approach

If you’re not familiar with how base conversion from decimal (base 10) to another base works, here's the process:

1. Divide the number by the base and store the remainder.
2. Update the number using integer division (only the whole number part).
3. Repeat until the number becomes 0.
4. Reverse the collected remainders to get the result.

Let’s convert 49 to base 13:

Steps:

• $49 \mod 13 = 10 \rightarrow \text{store "A"}$
• $49 \div 13 = 3$(integer division, whole number only).
• $3 \mod 13 = 3 \rightarrow \text{store "3"}$
• $3 \div 13 = 0 \ \text{(stop)}$

So, the remainders are $[A, 3]$. After reversing them, the result is "3A" in base 13.

Here’s the code for the iterative approach where we reverse the result at the end:

In the above code, we are concatenating strings using , and every time we append to a string, Python creates a new string by allocating memory for both the current string and the new character. This operation takes $O(n + m)$, where $n$ is the length of the first string and $m$ is the length of the second string.

In the worst case, string concatenation over multiple iterations becomes $O(n^2)$. This isn’t a big issue for small strings like in this problem, but for longer strings, we can improve the efficiency by using a list and joining it at the end.

Here’s the code using a list for collecting digits, avoiding repeated string concatenations:

This version avoids string concatenation overhead by building the result in a list and reversing it at the end, which operates in $O(n)$ time.

Recursive Approach

The recursive approach follows the same logic as the iterative one but works by breaking the number down step-by-step using recursion. Each recursive call handles a smaller part of the number and builds the result as it "returns" from the recursive calls.

Base Case:

• If the number is less than 13, directly return its base 13 equivalent.

Recursive Case:

• Divide the number by 13, recursively call the function with the quotient, and then append the remainder at the end.

This method handles negative numbers by converting the absolute value to base 13 and then prepending a minus sign.