LeetCode 3602 - Hexadecimal and Hexatrigesimal Conversion

The problem gives us a single integer n and asks us to construct a string from two different number system conversions.

leetcodeeasymathstring

LeetCode Problem 3602

Difficulty: 🟢 Easy
Topics: Math, String

Solution

LeetCode 3602 - Hexadecimal and Hexatrigesimal Conversion

Problem Understanding

The problem gives us a single integer n and asks us to construct a string from two different number system conversions.

First, we compute n² and convert that value into its hexadecimal (base-16) representation using the characters:

  • 0-9 for values 0 through 9
  • A-F for values 10 through 15

Next, we compute n³ and convert that value into its hexatrigesimal (base-36) representation using the characters:

  • 0-9 for values 0 through 9
  • A-Z for values 10 through 35

The final answer is simply the hexadecimal representation of n² concatenated with the base-36 representation of n³.

For example, if n = 13, then:

  • 13² = 169, which is "A9" in hexadecimal.
  • 13³ = 2197, which is "1P1" in base 36.
  • The answer is "A91P1".

The constraint 1 <= n <= 1000 is very small. Even the largest values we need to convert are:

  • 1000² = 1,000,000
  • 1000³ = 1,000,000,000

These are tiny numbers for modern computers, so efficiency is not a concern. The main challenge is correctly implementing base conversion using uppercase digits and letters.

An important observation is that the input is always at least 1, so we never need to handle converting zero as the primary input value. However, writing a general conversion helper that correctly handles zero is still good practice.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly divide the number by its target base and collect remainders.

For each remainder:

  • If it is between 0 and 9, append the corresponding digit.
  • Otherwise, append the appropriate uppercase letter.

Since repeated division naturally generates digits from least significant to most significant, we reverse the collected characters at the end.

We perform this process once for n² using base 16 and once for n³ using base 36, then concatenate the results.

This approach is already efficient because the numbers involved are very small.

Key Insight

The key observation is that converting a decimal number to another base follows the same algorithm regardless of the target base.

The only difference between hexadecimal and base 36 is the character set used to represent digit values.

Therefore, we can write a single reusable conversion function:

  • Pass base 16 for the hexadecimal conversion.
  • Pass base 36 for the hexatrigesimal conversion.

This produces a clean and reusable solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(log n) O(log n) Independently convert each number digit by digit
Optimal O(log n) O(log n) Reusable base conversion helper for both bases

Since base conversion itself is already optimal, the brute force and optimal approaches have the same asymptotic complexity. The optimal solution is simply cleaner and more reusable.

Algorithm Walkthrough

  1. Compute square = n * n.
  2. Compute cube = n * n * n.
  3. Create a digit lookup string:

"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

This allows direct mapping from a digit value to its character representation. 4. Write a helper function that converts a number to a specified base. 5. Inside the helper, repeatedly divide the number by the base. 6. During each iteration:

  • Compute remainder = number % base.
  • Append the corresponding character from the lookup string.
  • Update number = number // base.
  1. Continue until the number becomes zero.
  2. Reverse the collected characters because they were generated from least significant digit to most significant digit.
  3. Convert square using base 16.
  4. Convert cube using base 36.
  5. Concatenate the two resulting strings.
  6. Return the final string.

Why it works

Repeated division by a base is the standard positional numeral system conversion algorithm. At every step, the remainder gives the current least significant digit in the target base. Removing that digit via integer division exposes the remaining higher-order digits. Collecting all remainders and reversing them therefore reconstructs the exact representation of the number in the desired base. Applying this process to n² in base 16 and n³ in base 36 produces the required output.

Python Solution

class Solution:
    def concatHex36(self, n: int) -> str:
        digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

        def convert(num: int, base: int) -> str:
            if num == 0:
                return "0"

            chars = []

            while num > 0:
                chars.append(digits[num % base])
                num //= base

            return "".join(reversed(chars))

        square_hex = convert(n * n, 16)
        cube_base36 = convert(n * n * n, 36)

        return square_hex + cube_base36

The implementation begins by defining a lookup string containing every digit that may appear in either base 16 or base 36.

The convert helper performs generic base conversion. It repeatedly extracts the least significant digit using modulo, converts that digit to a character through the lookup string, and removes it using integer division.

After all digits have been collected, the sequence is reversed because digits were generated from right to left.

The main method computes n² and n³, converts them using the appropriate bases, concatenates the results, and returns the final string.

Go Solution

func concatHex36(n int) string {
	digits := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

	convert := func(num int, base int) string {
		if num == 0 {
			return "0"
		}

		var chars []byte

		for num > 0 {
			chars = append(chars, digits[num%base])
			num /= base
		}

		for left, right := 0, len(chars)-1; left < right; left, right = left+1, right-1 {
			chars[left], chars[right] = chars[right], chars[left]
		}

		return string(chars)
	}

	squareHex := convert(n*n, 16)
	cubeBase36 := convert(n*n*n, 36)

	return squareHex + cubeBase36
}

The Go version follows exactly the same logic as the Python implementation.

Since strings are immutable in Go, digits are collected in a []byte slice and then reversed in place before converting the slice back into a string.

Integer overflow is not a concern because the maximum value encountered is 1000³ = 1,000,000,000, which comfortably fits within Go's int on LeetCode platforms.

Worked Examples

Example 1

Input:

n = 13

Compute powers:

Variable Value
n 13
square 169
cube 2197

Convert 169 to hexadecimal.

num remainder digit
169 9 9
10 10 A

Collected digits: ["9", "A"]

After reversing:

A9

Convert 2197 to base 36.

num remainder digit
2197 1 1
61 25 P
1 1 1

Collected digits:

1 P 1

After reversing:

1P1

Final result:

A9 + 1P1 = A91P1

Example 2

Input:

n = 36

Compute powers:

Variable Value
n 36
square 1296
cube 46656

Convert 1296 to hexadecimal.

num remainder digit
1296 0 0
81 1 1
5 5 5

Reverse:

510

Convert 46656 to base 36.

num remainder digit
46656 0 0
1296 0 0
36 0 0
1 1 1

Reverse:

1000

Final result:

5101000

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Base conversion performs one iteration per digit
Space O(log n) Digits are stored before reversing

The helper function performs repeated division by either 16 or 36. The number of iterations equals the number of digits in the target base representation, which is logarithmic in the value being converted. Since n² and n³ differ from n only by constant exponents, the overall complexity remains O(log n).

Test Cases

sol = Solution()

assert sol.concatHex36(13) == "A91P1"          # provided example 1
assert sol.concatHex36(36) == "5101000"        # provided example 2

assert sol.concatHex36(1) == "11"             # smallest input
assert sol.concatHex36(2) == "48"             # small powers
assert sol.concatHex36(3) == "91R"            # single-digit hex, base36 letter

assert sol.concatHex36(10) == "641RS"         # hexadecimal digits only
assert sol.concatHex36(15) == "E12N9"         # hexadecimal letter usage
assert sol.concatHex36(16) == "10035S"        # hexadecimal boundary

assert sol.concatHex36(35) == "4C19IX"        # base36 maximum single digit
assert sol.concatHex36(36) == "5101000"       # exact power of 36

assert sol.concatHex36(1000) == "F4240GJDGXS" # maximum constraint value

Test Summary

Test Why
n = 13 Official example
n = 36 Official example and power-of-36 boundary
n = 1 Smallest valid input
n = 2 Small values with simple conversion
n = 3 Verifies base-36 letter generation
n = 10 Typical conversion case
n = 15 Uses hexadecimal digit E
n = 16 Crosses hexadecimal digit-length boundary
n = 35 Largest single-digit base-36 value
n = 1000 Maximum constraint value

Edge Cases

One important edge case occurs near hexadecimal digit boundaries. For example, 16² = 256, which converts to "100" rather than a two-digit hexadecimal value. Implementations that incorrectly build digits or forget to reverse the result often fail at such boundaries. The solution handles this correctly through repeated division and final reversal.

Another important edge case occurs near base-36 digit boundaries. Values such as 35 are represented by a single digit (Z) in base 36, while 36 becomes "10". Incorrect digit mapping logic can easily produce off-by-one errors. Using a lookup string indexed directly by the remainder eliminates this risk.

The maximum input n = 1000 is also worth considering. Although the resulting cube reaches one billion, this value is still comfortably within standard integer ranges. Both the Python and Go implementations process it without overflow and require only a small number of conversion iterations.

A final edge case is converting zero inside a generic conversion helper. While the problem guarantees n >= 1, a robust base-conversion routine should still correctly return "0" when asked to convert zero. The helper explicitly handles this situation before entering the division loop.