LeetCode 1271 - Hexspeak

Difficulty: 🟢 Easy
Topics: Math, String

Solution

Problem Understanding

The problem asks us to convert a decimal number given as a string into its Hexspeak representation. Hexspeak is derived from the hexadecimal representation of the number, with a simple character substitution: '0' becomes 'O' and '1' becomes 'I'. A valid Hexspeak string can only contain the characters {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. If the resulting hexadecimal string contains any other digit (i.e., 2 through 9), it is invalid and should return "ERROR".

The input is a string num representing an integer n with no leading zeros. The constraints tell us that num can be very large (up to 1 trillion), so direct integer conversion in languages with fixed-width integers may require careful handling. The key edge cases include very small numbers like "1", very large numbers near 10^12, and numbers that produce hexadecimal digits outside the allowed Hexspeak set.

The output is either a string representing the valid Hexspeak conversion or "ERROR" if the conversion contains invalid characters.

Approaches

Brute Force Approach

A brute force approach would convert the input string to an integer, compute its hexadecimal representation, replace '0' with 'O' and '1' with 'I', and then check every character to see if it belongs to the valid Hexspeak set. This approach works correctly because it directly follows the problem statement, but it may be inefficient if repeatedly converting very large numbers character by character or if done without mapping tables. The complexity is acceptable here because the numbers are at most 12 digits, but conceptually, this approach is not elegant.

Optimal Approach

The key observation for an optimal solution is that we can build the Hexspeak string directly by repeatedly dividing the number by 16 and examining the remainder. For each remainder, we can map valid values to the allowed Hexspeak characters: 0 → O, 1 → I, 10-15 → A-F. Any remainder outside these mappings immediately signals "ERROR". This approach avoids converting the entire number to a hexadecimal string first and directly constructs the answer in a single pass from least significant to most significant digit.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log n)	O(log n)	Convert number to hex string, map characters, validate
Optimal	O(log n)	O(log n)	Compute remainders modulo 16, map directly, build string

Algorithm Walkthrough

Convert the input string num to an integer n.
Initialize an empty list result to store the Hexspeak characters in reverse order.
While n is greater than 0, do the following:
Compute remainder = n % 16.
If remainder is 0, append 'O' to result.
If remainder is 1, append 'I' to result.
If remainder is between 10 and 15, append the corresponding hexadecimal character 'A' to 'F'.
If remainder is between 2 and 9, return "ERROR" immediately.
Update n = n // 16 to process the next digit.
Reverse the result list to obtain the correct order.
Join the list into a string and return it.

Why it works: By processing the number in base 16 from least significant to most significant digit and directly mapping to valid Hexspeak characters, we ensure that any invalid digit immediately triggers "ERROR". Reversing the list at the end correctly aligns the characters, preserving the proper hexadecimal order.

Python Solution

class Solution:
    def toHexspeak(self, num: str) -> str:
        n = int(num)
        hexspeak_chars = []
        
        while n > 0:
            remainder = n % 16
            if remainder == 0:
                hexspeak_chars.append('O')
            elif remainder == 1:
                hexspeak_chars.append('I')
            elif 10 <= remainder <= 15:
                hexspeak_chars.append(chr(ord('A') + remainder - 10))
            else:
                return "ERROR"
            n //= 16
        
        return ''.join(reversed(hexspeak_chars))

In this implementation, we first convert the string input into an integer. Then, we process the number modulo 16 to extract each hexadecimal digit. Valid digits are directly mapped to Hexspeak characters while invalid digits immediately trigger "ERROR". Finally, the list of characters is reversed and joined into a single string.

Go Solution

func toHexspeak(num string) string {
    n := 0
    for _, c := range num {
        n = n*10 + int(c-'0')
    }

    if n == 0 {
        return "O"
    }

    hexspeak := []byte{}
    for n > 0 {
        remainder := n % 16
        if remainder == 0 {
            hexspeak = append(hexspeak, 'O')
        } else if remainder == 1 {
            hexspeak = append(hexspeak, 'I')
        } else if remainder >= 10 && remainder <= 15 {
            hexspeak = append(hexspeak, byte('A'+remainder-10))
        } else {
            return "ERROR"
        }
        n /= 16
    }

    // reverse slice
    for i, j := 0, len(hexspeak)-1; i < j; i, j = i+1, j-1 {
        hexspeak[i], hexspeak[j] = hexspeak[j], hexspeak[i]
    }

    return string(hexspeak)
}

In Go, we manually convert the string input to an integer because Go does not implicitly handle large string-to-int conversions in the same way Python does. We then follow the same remainder-based processing and map to Hexspeak characters, reversing the slice at the end.

Worked Examples

Example 1: num = "257"

Convert to integer: n = 257.
Compute 257 % 16 = 1, append 'I' → hexspeak_chars = ['I'].
Update n = 257 // 16 = 16.
Compute 16 % 16 = 0, append 'O' → hexspeak_chars = ['I', 'O'].
Update n = 16 // 16 = 1.
Compute 1 % 16 = 1, append 'I' → hexspeak_chars = ['I', 'O', 'I'].
Update n = 1 // 16 = 0.
Reverse → ['I', 'O', 'I'] → "IOI".

Example 2: num = "3"

Convert to integer: n = 3.
Compute 3 % 16 = 3, which is invalid → return "ERROR".

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	We divide the number by 16 repeatedly, giving a logarithmic number of steps in base 16.
Space	O(log n)	The number of characters stored in the result list is proportional to the number of hexadecimal digits.

The complexity is efficient because the input number is at most 10^12, which requires at most 12 hexadecimal digits.

Test Cases

# Provided examples
assert Solution().toHexspeak("257") == "IOI"  # Example 1
assert Solution().toHexspeak("3") == "ERROR"  # Example 2

# Edge cases
assert Solution().toHexspeak("1") == "I"  # Smallest valid number
assert Solution().toHexspeak("16") == "IO"  # Powers of 16
assert Solution().toHexspeak("15") == "F"  # Single hex character
assert Solution().toHexspeak("10") == "A"  # Maps to 'A' in Hexspeak
assert Solution().toHexspeak("4095") == "FFF"  # Max 3-digit hex number
assert Solution().toHexspeak("1000000000000") == "ERROR"  # Very large number with invalid digits

Test	Why
`"257"`	Regular case converting to valid Hexspeak
`"3"`	Invalid hexadecimal digit triggers `"ERROR"`
`"1"`	Smallest valid input mapped to `'I'`
`"16"`	Multiple digit conversion including `'O'`
`"15"`	Single hex character `'F'`
`"10"`	Valid single-character Hexspeak `'A'`
`"4095"`	All digits valid `'F'` repeated
`"1000000000000"`	Very large number with invalid digits triggers `"ERROR"`

Edge Cases

Case 1: Minimum input "1"

This is the smallest valid decimal input. It converts to 1 in hex, mapped to 'I'. This tests that the algorithm correctly handles