Hexadecimal and Hexatrigesimal Conversion - Solution & Explanation

Problem Overview: Given an integer, convert it into two different numeral systems: hexadecimal (base 16) and hexatrigesimal (base 36). The task is essentially a base conversion problem where digits beyond 9 are represented using alphabet characters. You generate the string representation for both bases.

Approach 1: Built-in Base Conversion (O(log n) time, O(log n) space)

Most languages provide built-in utilities for base conversion. For example, Python exposes hex() and formatting utilities, while Java and C++ provide methods such as Integer.toString(num, base). These functions internally perform repeated division by the base and map remainders to characters (0-9, a-z). This approach keeps the implementation short and reliable. Time complexity is O(log n) because the number of digits in base 16 or base 36 grows logarithmically with the input value. Space complexity is also O(log n) for the resulting string.

Approach 2: Simulation with Repeated Division (O(log n) time, O(log n) space)

The manual method simulates how base conversion works mathematically. Repeatedly divide the number by the target base and record the remainder. Each remainder corresponds to a digit in the new base. Values 0-9 map directly to characters, while values 10-15 (hex) or 10-35 (base36) map to letters using a lookup string such as "0123456789abcdefghijklmnopqrstuvwxyz". Append digits as you compute them, then reverse the result to produce the correct order.

This approach makes the algorithm explicit. You control digit mapping, handle edge cases like zero, and can easily adapt the logic to other bases. Each iteration reduces the number by dividing it by the base, so the loop runs roughly log_base(n) times. That yields O(log n) time complexity and O(log n) space for storing digits.

Conceptually, this is a combination of Math and String manipulation. The math part determines remainders and base reduction, while the string part handles character mapping and result construction. Many base-conversion problems follow this exact pattern, so mastering the simulation approach makes similar problems straightforward.

Recommended for interviews: The simulation approach. Interviewers expect you to understand how base conversion works internally rather than relying entirely on library helpers. Showing the repeated division process demonstrates understanding of number systems and careful string construction. Mentioning the built-in shortcut is fine, but implementing the simulation proves stronger problem-solving fundamentals.