Skip to content

3602. Hexadecimal and Hexatrigesimal Conversion

SourceBiweekly Contest 160 Q1DifficultyEasyRating1305

Description

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

Solutions

Solution 1: Simulation

Thinking

We need \(n^2\) in base \(16\) and \(n^3\) in base \(36\). Built-in converters usually cover only hexadecimal, so the two bases would otherwise diverge.

Any base is obtained by repeated modulo and division. Factor \(f(x,k)\): write a digit when the remainder is at most \(9\), otherwise a letter, then reverse the low-order sequence.

With \(x=n^2\) and \(y=n^3\), return \(f(x,16)+f(y,36)\). The loop length is logarithmic in \(n\).

We define a function \(\textit{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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def concatHex36(self, n: int) -> str:
        def f(x: int, k: int) -> str:
            res = []
            while x:
                v = x % k
                if v <= 9:
                    res.append(str(v))
                else:
                    res.append(chr(ord("A") + v - 10))
                x //= k
            return "".join(res[::-1])

        x, y = n**2, n**3
        return f(x, 16) + f(y, 36)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String concatHex36(int n) {
        int x = n * n;
        int y = n * n * n;
        return f(x, 16) + f(y, 36);
    }

    private String f(int x, int k) {
        StringBuilder res = new StringBuilder();
        while (x > 0) {
            int v = x % k;
            if (v <= 9) {
                res.append((char) ('0' + v));
            } else {
                res.append((char) ('A' + v - 10));
            }
            x /= k;
        }
        return res.reverse().toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string concatHex36(int n) {
        int x = n * n;
        int y = n * n * n;
        return f(x, 16) + f(y, 36);
    }

private:
    string f(int x, int k) {
        string res;
        while (x > 0) {
            int v = x % k;
            if (v <= 9) {
                res += char('0' + v);
            } else {
                res += char('A' + v - 10);
            }
            x /= k;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func concatHex36(n int) string {
    x := n * n
    y := n * n * n
    return f(x, 16) + f(y, 36)
}

func f(x, k int) string {
    res := []byte{}
    for x > 0 {
        v := x % k
        if v <= 9 {
            res = append(res, byte('0'+v))
        } else {
            res = append(res, byte('A'+v-10))
        }
        x /= k
    }
    for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
        res[i], res[j] = res[j], res[i]
    }
    return string(res)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function concatHex36(n: number): string {
    function f(x: number, k: number): string {
        const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
        let res = '';
        while (x > 0) {
            const v = x % k;
            res = digits[v] + res;
            x = Math.floor(x / k);
        }
        return res;
    }

    const x = n * n;
    const y = n * n * n;
    return f(x, 16) + f(y, 36);
}

Comments