3602. Hexadecimal and Hexatrigesimal Conversion

EasyMathString

Problem Description

You are given an integer n.

Return the concatenation of the hexadecimal representation of n^2 and the hexatrigesimal representation of n^3.

A hexadecimal number is a base-16 numeral system that uses the digits 0–9 and the uppercase letters A–F to represent values from 0 to 15.

A hexatrigesimal number is a base-36 numeral system that uses the digits 0–9 and the uppercase letters A–Z to represent values from 0 to 35.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, first notice that we need to represent numbers in different bases: hexadecimal (base 16) and hexatrigesimal (base 36). We can use a straightforward method to convert any integer to a string in any base by repeatedly dividing by the base and recording the remainders, which give the digits from lowest to highest. For values 10 and above, we substitute with letters (like "A" for 10, "B" for 11, etc.). Applying this to n^2 for hexadecimal and n^3 for base 36, then combining the results, gives the answer.

Solution Approach

We define a helper function f(x, k) that converts the integer x to a string in base k. This is done by repeatedly dividing x by k, each time taking the remainder as the next digit (starting from the least significant digit). If the remainder is less than or equal to 9, we use the corresponding character '0' to '9'. If the remainder is greater than 9, we map it to uppercase letters ('A' to 'Z').

For the problem, we first compute n^2 and n^3 for the given input n. The value n^2 is converted to a hexadecimal string by calling f(n^2, 16), and n^3 is converted to a base-36 (hexatrigesimal) string by calling f(n^3, 36). Finally, we concatenate both resulting strings and return the result.

This approach directly simulates the number conversion process for any arbitrary base, which is an efficient and generic solution and avoids using language-specific conversion functions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Take n = 5 as an example.

Step 1: Compute n^2 and n^3

n^2 = 25
n^3 = 125

Step 2: Convert n^2 (25) to hexadecimal (base 16)

25 divided by 16 gives quotient 1, remainder 9. (First digit from the right: 9)
1 divided by 16 gives quotient 0, remainder 1. (Next digit: 1)
Read digits in reverse order: '19'

Step 3: Convert n^3 (125) to hexatrigesimal (base 36)

125 divided by 36 gives quotient 3, remainder 17. (First digit from the right. 17 maps to 'H', since A=10, B=11,..., H=17)
3 divided by 36 gives quotient 0, remainder 3. (Next digit: 3)
Read digits in reverse order: '3H'

Step 4: Concatenate both results

Hexadecimal of 25: '19'
Hexatrigesimal of 125: '3H'
Final answer: '193H'

This example shows how to convert numbers into their respective bases using repeated division and mapping digits above 9 to letters, then concatenate the strings to form the result.

Solution Implementation

1class Solution:
2    def concatHex36(self, n: int) -> str:
3        # Helper function to convert an integer x to base-k string
4        def f(x: int, k: int) -> str:
5            if x == 0:  # Handle 0 case
6                return "0"
7            digits = []
8            while x > 0:
9                remainder = x % k
10                if remainder <= 9:
11                    # For digits 0-9, use their string representation
12                    digits.append(str(remainder))
13                else:
14                    # For digits >= 10, map to 'A'-'Z'
15                    digits.append(chr(ord('A') + remainder - 10))
16                x //= k
17            # Reverse the collected digits and join as a string
18            return ''.join(reversed(digits))
19
20        # Calculate square and cube of n
21        square = n ** 2
22        cube = n ** 3
23
24        # Convert square to hexadecimal and cube to base-36, then concatenate
25        return f(square, 16) + f(cube, 36)
26

1class Solution {
2    /**
3     * Given an integer n, this method calculates two values:
4     *   - x = n squared (n^2), and converts x to a string in base 16 (hexadecimal)
5     *   - y = n cubed (n^3), and converts y to a string in base 36
6     * Then concatenates the two string representations.
7     */
8    public String concatHex36(int n) {
9        int x = n * n;         // x is n squared
10        int y = n * n * n;     // y is n cubed
11        return f(x, 16) + f(y, 36);
12    }
13
14    /**
15     * Converts the integer x to a string in base k.
16     * For bases above 10, uses uppercase letters for digits >= 10.
17     *
18     * @param x the number to convert
19     * @param k the base (e.g., 16 for hexadecimal, 36 for base-36)
20     * @return x represented as a string in base k
21     */
22    private String f(int x, int k) {
23        if (x == 0) {
24            return "0";
25        }
26        StringBuilder result = new StringBuilder();
27        while (x > 0) {
28            int digit = x % k;
29            if (digit <= 9) {
30                result.append((char) ('0' + digit));           // For digits 0-9
31            } else {
32                result.append((char) ('A' + digit - 10));      // For digits 10 and above, as uppercase letters
33            }
34            x /= k;
35        }
36        result.reverse(); // Digits are added in reverse order
37        return result.toString();
38    }
39}
40

1#include <string>
2#include <algorithm>
3
4class Solution {
5public:
6    // Concatenates the hexadecimal (base 16) representation of n^2
7    // and the base-36 representation of n^3
8    std::string concatHex36(int n) {
9        int square = n * n;
10        int cube = n * n * n;
11        return f(square, 16) + f(cube, 36);
12    }
13
14private:
15    // Converts integer x to a string in base-k numeral system
16    std::string f(int x, int base) {
17        if (x == 0) return "0";
18        std::string result;
19        while (x > 0) {
20            int digit = x % base;
21            // 0-9 map to '0'-'9', 10-35 map to 'A'-'Z'
22            if (digit < 10) {
23                result += static_cast<char>('0' + digit);
24            } else {
25                result += static_cast<char>('A' + digit - 10);
26            }
27            x /= base;
28        }
29        std::reverse(result.begin(), result.end());
30        return result;
31    }
32};
33

1/**
2 * Converts a number `n` to two concatenated strings:
3 * - `n * n` in hexadecimal (base 16)
4 * - `n * n * n` in base 36
5 * Example: concatHex36(10) returns "64RS0"
6 */
7function concatHex36(n: number): string {
8    /**
9     * Converts number x to a string in base k using digits 0-9 and A-Z.
10     * @param x - The number to convert.
11     * @param k - The base to convert to (max 36).
12     * @returns String representation of x in base k.
13     */
14    function f(x: number, k: number): string {
15        const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
16        let result = '';
17        while (x > 0) {
18            const remainder = x % k;
19            result = digits[remainder] + result;
20            x = Math.floor(x / k);
21        }
22        return result;
23    }
24
25    // Calculate square of n for hexadecimal conversion
26    const x = n * n;
27
28    // Calculate cube of n for base 36 conversion
29    const y = n * n * n;
30
31    // Concatenate hexadecimal and base-36 results
32    return f(x, 16) + f(y, 36);
33}
34

Time and Space Complexity

The time complexity is O(\log n). This is because converting both n^2 to hexadecimal and n^3 to base-36 formats through the function f(x, k) involves repeated division by the base k, which takes at most O(\log_k(x)) steps for each value. Since x = n^2 and y = n^3, this is O(\log n) operations for each conversion; however, both are within the same overall O(\log n) bound.

The space complexity is O(1). Although the res list in the conversion function temporarily stores digits, its length is bounded by the number of digits in the base representation, which is at most O(\log n). However, since the output string's storage is not counted as auxiliary space and all other extra space use is constant, the space complexity is considered O(1).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear Search

Binary Search

Quick Select

Hash Set

I don't know