405. Convert a Number to Hexadecimal
Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 44.5%
Problem Breakdown
The problem requires converting an integer to its hexadecimal representation. The input is a 32-bit signed integer, which can be positive or negative. For negative numbers, the two’s complement method should be used. The output must be a string of hexadecimal digits (0-9, a-f), with all letters in lowercase. The string should not have leading zeros unless the number itself is zero.
Inputs:
- A 32-bit signed integer
Outputs:
- A string representing the hexadecimal equivalent of the input integer
Implicit Constraints:
- Negative numbers are handled using two’s complement.
- Hexadecimal letters must be lowercase.
- No extra leading zeros in the output unless the number is zero.
Tricky Edge Cases:
- Zero as input should return “0”.
- Negative numbers, especially those close to the 32-bit signed integer limit.
- Large positive numbers that require multiple hexadecimal digits.
Intuition
A brute-force approach would involve repeatedly dividing the number by 16 and mapping remainders to hexadecimal characters. However, this method is inefficient for negative numbers due to handling two’s complement manually. A better approach involves using bitwise operations to extract each hexadecimal digit directly from the binary representation of the number. This leverages the fact that a byte (8 bits) can be represented by exactly two hexadecimal digits.
Approach
-
Initialize Constants and Variables:
- Define a string
hex_charscontaining all possible hexadecimal characters (0-9,a-f). - Initialize an empty list
resultto store the hexadecimal digits.
- Define a string
-
Handle Zero Case:
- If the input number is zero, directly return “0”.
-
Convert Negative Numbers to Two’s Complement:
- For negative numbers, convert them to their two’s complement representation by adding (2^{32}) (4294967296).
-
Extract Hexadecimal Digits:
- Use a loop to extract each hexadecimal digit from the number:
- Mask the last 4 bits of the number using
num & 15to get the remainder when divided by 16. - Map this remainder to its corresponding hexadecimal character using
hex_chars. - Append this character to the
resultlist. - Right shift the number by 4 bits (
num >>= 4) to process the next set of 4 bits.
- Mask the last 4 bits of the number using
- Use a loop to extract each hexadecimal digit from the number:
-
Construct the Result String:
- Reverse the
resultlist since the digits were extracted from least significant to most significant. - Join the characters in the list to form the final hexadecimal string.
- Reverse the
Complexity Analysis
- Time Complexity: (O(1)) because the number of bits (32) is fixed, and we process each 4-bit chunk exactly once.
- Space Complexity: (O(1)) for storing the result list, which will have at most 8 characters (for the maximum 32-bit unsigned integer).
Solution
def toHex(num: int) -> str:
hex_chars = "0123456789abcdef"
result = []
if num == 0:
return "0"
# Handle negative numbers using two's complement
if num < 0:
num += 2**32
while num > 0:
result.append(hex_chars[num & 15])
num >>= 4
return ''.join(reversed(result))
Edge Cases Handled
- Zero Input: The function returns “0” as expected.
- Negative Numbers: The two’s complement conversion ensures correct hexadecimal representation for negative numbers.
- Large Positive Numbers: The loop processes all bits of the number, ensuring accurate conversion even for large values.