1271. Hexspeak
Model: qwen2.5-coder:14b
Topics: Math,String
FAANG asked: 0
Acceptance rate: 55.5%
Problem Breakdown
The problem requires converting a decimal number given as a string into its Hexspeak representation. The steps are:
- Convert the decimal number to an uppercase hexadecimal string.
- Replace all occurrences of ‘0’ with ‘O’ and ‘1’ with ‘I’.
- Check if the resulting string contains only valid Hexspeak characters: {“A”, “B”, “C”, “D”, “E”, “F”, “I”, “O”}.
- If valid, return the Hexspeak representation; otherwise, return “ERROR”.
Inputs: A string num representing a decimal integer N.
Outputs: The Hexspeak representation of N if valid, or “ERROR”.
Implicit Constraints:
- The input number is within the range [1, 10^12].
- There are no leading zeros in the input string.
- All answers must be in uppercase letters.
Intuition
A brute-force approach would involve converting the decimal to hexadecimal and then manually replacing characters. However, this could lead to inefficiencies and potential errors in character replacement. The key insight is to use Python’s built-in functions for conversion and validation, ensuring both correctness and efficiency.
Starting from a brute-force method where we manually handle each digit conversion and replacement would be inefficient and error-prone. Instead, leveraging Python’s int to convert the string to an integer, then using hex() to get the hexadecimal representation, and finally validating the characters in one pass is more efficient.
Approach
- Convert the input string
numto an integer. - Use the
hex()function to convert the integer to a hexadecimal string. - Remove the ‘0x’ prefix from the hexadecimal string.
- Replace all occurrences of ‘0’ with ‘O’ and ‘1’ with ‘I’.
- Check if the resulting string contains only valid Hexspeak characters.
- If valid, return the modified string; otherwise, return “ERROR”.
Complexity Analysis
- Time Complexity: O(n), where n is the length of the hexadecimal string after conversion. This is because we perform a single pass to replace characters and validate them.
- Space Complexity: O(n) for storing the hexadecimal string and the final result.
Solution
def toHexspeak(num: str) -> str:
# Convert the input number to an integer
decimal_number = int(num)
# Convert the integer to a hexadecimal string and remove the '0x' prefix
hex_string = hex(decimal_number)[2:].upper()
# Replace '0' with 'O' and '1' with 'I'
hexspeak_chars = {'0': 'O', '1': 'I'}
result = []
for char in hex_string:
if char in hexspeak_chars:
result.append(hexspeak_chars[char])
elif char not in "ABCDEF":
return "ERROR"
else:
result.append(char)
# Join the list into a string and return
return ''.join(result)
Edge Cases Handled
- Single-digit numbers: The approach correctly handles single-digit inputs like “3” which should return “ERROR”.
- Numbers with leading zeros in hexadecimal representation: Although not possible due to input constraints, the code inherently handles such cases by using
hex(). - Large numbers up to 10^12: Python’s
intandhex()functions can handle large integers efficiently. - Invalid characters after replacement: The code checks for invalid characters and returns “ERROR” if any are found.