Hexadecimal and Hexatrigesimal Conversion

Difficulty: Easy | Acceptance: 80.90% | Paid: No Topics: Math, String

You are given a string num representing a positive integer in hexadecimal (base 16).

Return the string representation of the same integer in hexadecimal (base 36).

Hexadecimal digits are the lowercase characters 0 to 9 and a to f. Hexadecimal does not contain leading zeros.

Hexadecimal digits are the lowercase characters 0 to 9 and a to z.

• Examples
• Constraints
• Approach 1: Built-in BigInt Libraries
• Approach 2: Manual Base Conversion (String Arithmetic)

Examples

Example 1

Input: num = "1a"
Output: "q"
Explanation: 1a in hexadecimal is 26 in decimal. 26 in hexadecimal is "q".

Example 2

Input: num = "ff"
Output: "73"
Explanation: ff in hexadecimal is 255 in decimal. 255 = 7 * 36 + 3. So it is "73".

Constraints

1 <= num.length <= 100
num consists of lowercase English letters and digits.
num does not have leading zeros.

Approach 1: Built-in BigInt Libraries

Intuition Most modern programming languages provide built-in support for arbitrary-precision integers (BigInt). We can leverage these libraries to parse the hexadecimal string into a BigInt and then format it into a base-36 string.

Steps

• Parse the input string num as a base-16 integer to obtain a BigInt value.
• Convert the BigInt value to a string representation in base-36.
• Return the resulting string.

class Solution:
    def toHexatrigesimal(self, num: str) -> str:
        # Python int handles arbitrary precision automatically
        val = int(num, 16)
        if val == 0:
            return "0"
        chars = "0123456789abcdefghijklmnopqrstuvwxyz"
        res = []
        while val > 0:
            res.append(chars[val % 36])
            val //= 36
        return "".join(reversed(res))

Complexity

• Time: O(N) where N is the length of the string. (Assuming BigInt operations are linear or near-linear for this size).
• Space: O(N) to store the result.
• Notes: This is the most concise solution for languages with built-in BigInt support. For C++, a manual implementation is required.

Approach 2: Manual Base Conversion (String Arithmetic)

Intuition For languages or environments without BigInt support, we simulate arithmetic operations on strings. We first convert the hexadecimal string to a decimal string by iterating and multiplying by 16. Then, we repeatedly divide the decimal string by 36 to extract base-36 digits.

Steps

• Implement helper functions to add an integer to a decimal string and multiply a decimal string by an integer.
• Convert the input hexadecimal string to a decimal string using the helpers (processing digit by digit).
• Repeatedly divide the decimal string by 36. The remainder of each division corresponds to a digit in the base-36 result.
• Construct the result string from the remainders.

class Solution:
    def toHexadecimal(self, num: str) -> str:
        dec = "0"
        for c in num:
            val = int(c, 16)
            # Multiply dec by 16
            carry = 0
            mul_res = []
            for ch in reversed(dec):
                temp = (int(ch) * 16) + carry
                mul_res.append(str(temp % 10))
                carry = temp // 10
            if carry:
                mul_res.append(str(carry))
            dec = "".join(reversed(mul_res))
            
            # Add val to dec
            carry = val
            add_res = []
            for ch in reversed(dec):
                temp = int(ch) + carry
                add_res.append(str(temp % 10))
                carry = temp // 10
            if carry:
                add_res.append(str(carry))
            dec = "".join(reversed(add_res))
        return dec

    def toHexatrigesimal(self, num: str) -> str:
        # Manual conversion without int(num, 16)
        dec = self.toHexadecimal(num)
        
        if dec == "0":
            return "0"
        
        chars = "0123456789abcdefghijklmnopqrstuvwxyz"
        res = []
        
        while dec != "0":
            rem = 0
            next_dec = []
            for ch in dec:
                curr = rem * 10 + int(ch)
                next_dec.append(str(curr // 36))
                rem = curr % 36
            
            # Remove leading zeros
            dec = "".join(next_dec).lstrip('0')
            if not dec: dec = "0"
            
            res.append(chars[rem])
            
        return "".join(reversed(res))

Complexity

• Time: O(N²) in the worst case, where N is the length of the string. This is because string arithmetic (multiplication/division) takes O(N) time, and we perform it O(N) times (once per digit).
• Space: O(N) to store intermediate string representations.
• Notes: This approach is universally applicable but significantly slower than built-in BigInt for very large numbers.