NUHMAN.com

📘 Problem Statement

Given an integer num, convert it to a hexadecimal string and return it. You must not use any built-in library for base-16 conversion.

Input:

• An integer num (−2^31 ≤ num ≤ 2^31 − 1).

Output:

• The hexadecimal string representation of the integer num.

Note:

• For negative numbers, the hexadecimal representation is 32-bit two’s complement.
• The answer must not include the prefix "0x".

🧠 Key Insight

Hexadecimal (or base-16) is a number system that uses 16 symbols: 0-9 for values 0-9, and a-f for values 10-15. Converting an integer to hexadecimal involves repeatedly dividing the number by 16 and storing the remainders, which correspond to the digits of the hexadecimal representation.

When converting:

• If the number is negative, we can use two’s complement to represent the negative number in hexadecimal format.
• The result should be a string, where the digits are the remainders from division by 16.

💡 Approach

To convert a number to hexadecimal:

1. Handle the Edge Case: If num is 0, simply return "0".
2. Positive Numbers: Repeatedly divide the number by 16 and collect the remainders. Each remainder corresponds to a hexadecimal digit.
3. Negative Numbers: Convert the number to two’s complement format for negative values by adding 2^32 and then applying the same conversion.
4. Construct the Hexadecimal String: After collecting all the remainders (in reverse order), map them to their hexadecimal characters (0-9, a-f) and concatenate them.

🐍 Python Code

python

class Solution:
    def toHex(self, num: int) -> str:
        # Edge case: when the number is 0
        if num == 0:
            return "0"
        
        # If the number is negative, convert it to its 32-bit two's complement
        if num < 0:
            num += 2**32
        
        # Mapping of remainders to hex digits
        hex_map = "0123456789abcdef"
        
        result = []
        
        # Repeatedly divide by 16 and store the remainders (in reverse order)
        while num > 0:
            result.append(hex_map[num % 16])
            num //= 16
        
        # Return the hex string by reversing the result list
        return ''.join(reversed(result))

🔍 Step-by-Step Explanation

1. Handle the Edge Case (num = 0):

python

if num == 0:
    return "0"

• If the input number is 0, return "0" directly as the hexadecimal representation of 0 is simply "0".

2. Convert Negative Numbers to Two's Complement:

python

if num < 0:
    num += 2**32

• For negative numbers, we add 2^32 to num to get its two’s complement representation. This ensures that we correctly handle negative numbers as per the 32-bit representation used in hexadecimal.

3. Hexadecimal Digit Mapping:

python

hex_map = "0123456789abcdef"

• The hex_map string provides a mapping from the remainder (0-15) to their corresponding hexadecimal characters (0-9, a-f).

4. Conversion Loop:

python

while num > 0:
    result.append(hex_map[num % 16])
    num //= 16

• In this loop, we repeatedly divide num by 16, getting the remainder each time (num % 16), which corresponds to a hexadecimal digit. This remainder is appended to the result list.
• We continue dividing num by 16 until num becomes zero.

5. Construct the Final String:

python

return ''.join(reversed(result))

• The remainders are collected in reverse order, so we reverse the list of results and concatenate them to form the final hexadecimal string.

💡 Example Walkthrough

Example 1:

python

Input:
num = 26

Output:
"1a"

• Step 1: Since num is positive, we proceed directly to the conversion.
• Step 2: Divide 26 by 16, the remainder is 10, which corresponds to the character 'a'.
• Step 3: Now divide 26 // 16 = 1, and the remainder is 1, which corresponds to the character '1'.
• Step 4: The result is '1a' after reversing the remainders.

Example 2:

python

Input:
num = -1

Output:
"ffffffff"

• Step 1: Since num is negative, we convert it to two's complement by adding 2^32 to num:
• num = -1 + 2^32 = 4294967295.
• Step 2: Now proceed with the same conversion logic for 4294967295.
• Step 3: The remainders correspond to the hexadecimal representation 'ffffffff'.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(log(N))Space ComplexityO(log(N))

• Time Complexity:
• The loop runs as long as num is greater than 0, dividing num by 16 each time. The number of iterations is proportional to the number of digits in the hexadecimal representation, which is O(log(N)) where N is the absolute value of the number.
• Space Complexity:
• The space complexity is also O(log(N)) because we store the digits of the hexadecimal number in a list.

🧵 Final Thoughts

LeetCode 405 provides a clear exercise in understanding number base conversions. The problem not only tests knowledge of hexadecimal representations but also demonstrates how to handle edge cases (such as negative numbers and zero) efficiently. The two’s complement method for negative numbers ensures we adhere to the 32-bit representation, which is essential in many real-world applications, especially when dealing with low-level systems or networking protocols.