Skip to main content
Talentd

Hexadecimal and Hexatrigesimal Conversion - Solution & Explanation

EasyMathString7 min readAsked at: Zopsmart
Practice this problem

Problem Statement

You are given an integer n.

Return the concatenation of the hexadecimal representation of n2 and the hexatrigesimal representation of n3.

A hexadecimal number is defined as 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 defined as a base-36 numeral system that uses the digits 0 – 9 and the uppercase letters A - Z to represent values from 0 to 35.

 

Example 1:

Input: n = 13

Output: "A91P1"

Explanation:

  • n2 = 13 * 13 = 169. In hexadecimal, it converts to (10 * 16) + 9 = 169, which corresponds to "A9".
  • n3 = 13 * 13 * 13 = 2197. In hexatrigesimal, it converts to (1 * 362) + (25 * 36) + 1 = 2197, which corresponds to "1P1".
  • Concatenating both results gives "A9" + "1P1" = "A91P1".

Example 2:

Input: n = 36

Output: "5101000"

Explanation:

  • n2 = 36 * 36 = 1296. In hexadecimal, it converts to (5 * 162) + (1 * 16) + 0 = 1296, which corresponds to "510".
  • n3 = 36 * 36 * 36 = 46656. In hexatrigesimal, it converts to (1 * 363) + (0 * 362) + (0 * 36) + 0 = 46656, which corresponds to "1000".
  • Concatenating both results gives "510" + "1000" = "5101000".

 

Constraints:

  • 1 <= n <= 1000

Approach Overview

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.

Solution

We define a function f(x, k), which converts an integer x to its string representation in base k. This function constructs the result string by repeatedly taking the modulus and dividing.

For a given integer n, we compute n^2 and n^3, then convert them to hexadecimal and base-36 strings, respectively. Finally, we concatenate these two strings and return the result.

The time complexity is O(log n), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Built-in Base ConversionO(log n)O(log n)When language utilities are allowed and you want the shortest implementation
Simulation with Repeated DivisionO(log n)O(log n)Preferred in interviews to demonstrate understanding of base conversion logic

Video Solution

Leetcode Biweekly Contest 160 - Q1. Hexadecimal and Hexatrigesimal Conversion • ADevOpsEngineer • 630 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Hexadecimal and Hexatrigesimal Conversion easy or hard?
The problem is considered Easy because it relies on a standard base conversion technique. Once you understand repeated division and digit mapping for values above 9, the implementation is straightforward. Most solutions are under 15–20 lines of code.
Hexadecimal and Hexatrigesimal Conversion Python/Java solution
Python implementations typically use a loop with remainder operations and a digit mapping string. Java, C++, Go, and TypeScript follow the same pattern: repeatedly divide by the base, append the mapped character, and reverse the result. Each implementation runs in O(log n) time and O(log n) space.
How to solve Hexadecimal and Hexatrigesimal Conversion in O(log n)?
Use repeated division by the base. While the number is greater than zero, compute remainder = n % base, convert it to the corresponding character using a digit lookup string, append it, then update n = n / base. Reverse the collected characters at the end. This process runs in O(log n) time.
What is the best approach for Hexadecimal and Hexatrigesimal Conversion?
The simulation approach using repeated division by the target base is the most common solution. At each step you compute the remainder, map it to a digit (0-9 or a-z), and divide the number by the base. This produces the representation in reverse order, which is then reversed to form the final string. The algorithm runs in O(log n) time.
Is Hexadecimal and Hexatrigesimal Conversion asked at Google/Amazon/Meta?
Base conversion and number system manipulation appear in interviews across many companies because they test understanding of math fundamentals and string construction. Variants of this problem show up in coding screens and system utility questions, especially when working with encoding formats.
What data structure is used in Hexadecimal and Hexatrigesimal Conversion?
The solution mainly uses strings or character arrays to build the converted number. A lookup string like "0123456789abcdefghijklmnopqrstuvwxyz" helps map numeric remainders to characters. Aside from simple variables, no complex data structures are required.
What is the time complexity of Hexadecimal and Hexatrigesimal Conversion?
The time complexity is O(log n) because each step divides the number by the base (16 or 36). The number of iterations equals the number of digits in the resulting representation. Space complexity is also O(log n) since the output string stores that many digits.

Ready to solve this problem?

Practice Hexadecimal and Hexatrigesimal Conversion with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer