Problem Description

Given an integer num, convert it to its hexadecimal representation as a string and return it. The hexadecimal representation should use lowercase letters ('a' to 'f') for digits greater than 9. For negative numbers, use two's complement hexadecimal representation for 32-bit integers.

• Do not use any library functions to directly convert or format the number.
• Input is a valid 32-bit signed integer (-231 ≤ num ≤ 231 - 1).
• Return the hexadecimal string representation without leading zeros (except for the number zero itself).

Thought Process

The problem asks for a manual conversion of an integer to its hexadecimal string, similar to how you might convert decimal to binary by repeatedly dividing by 2. Here, we divide by 16 and map the remainders to hexadecimal digits. For negative numbers, we must represent them as 32-bit unsigned values using two's complement, which means masking the number to get its correct bitwise representation.

A brute-force approach would be to use built-in formatting, but the problem restricts us from doing so. Instead, we need to handle the conversion ourselves, including edge cases like zero and negative numbers. Optimization isn't a major concern here since the conversion is straightforward, but we must be careful with bit manipulation for negative numbers.

Solution Approach

1. Hexadecimal Digits Mapping:
   • Create a mapping from 0-15 to their hexadecimal characters ('0'-'9', 'a'-'f').
2. Handle Zero:
   • If num is zero, return "0" immediately.
3. Two's Complement for Negatives:
   • If num is negative, convert it to its 32-bit unsigned equivalent by masking with 0xFFFFFFFF.
4. Repeated Division:
   • While num is not zero, repeatedly:
   • Find the remainder of num divided by 16.
   • Map the remainder to its hexadecimal character.
   • Append the character to the result (building the string in reverse).
   • Divide num by 16 (using integer division).
5. Reverse the Result:
   • Since we build the hexadecimal string from least significant digit to most, reverse the result before returning.

This approach ensures we handle both positive and negative numbers, avoid leading zeros, and do not use forbidden built-in functions.

Example Walkthrough

Let's walk through the conversion of num = -26:

1. Since num is negative, convert to 32-bit unsigned: num = -26 & 0xFFFFFFFF = 4294967270.
2. Initialize an empty result string.
3. First iteration: 4294967270 % 16 = 10 ('a'), 4294967270 // 16 = 268435454.
4. Second: 268435454 % 16 = 14 ('e'), 268435454 // 16 = 16777215.
5. Third: 16777215 % 16 = 15 ('f'), 16777215 // 16 = 1048575.
6. Continue until num becomes zero, collecting digits: ['a', 'e', 'f', 'f', 'f', 'f', 'f', 'f'] (in reverse).
7. Reverse the string to get "ffffffe6".

Thus, -26 is represented as "ffffffe6" in hexadecimal (32-bit two's complement).

Time and Space Complexity

• Brute-force (using built-ins): Would be O(1) due to fixed integer size, but not allowed here.
• Manual Conversion:
  • Time Complexity: O(1), since the number of iterations is at most 8 (for 32 bits, as 4 bits per hex digit).
  • Space Complexity: O(1), as the output string is at most 8 characters (excluding the edge case for zero).
• The approach is efficient, handling all cases with a small, constant number of steps.

Summary

To convert an integer to its hexadecimal string, we repeatedly divide by 16 and map remainders to hex digits, handling negative numbers using 32-bit two's complement. This approach is efficient, simple, and avoids forbidden built-ins, making it both robust and elegant. The key insight is using bit masking for negatives and building the result in reverse.

Code Implementation

class Solution:
    def toHex(self, num: int) -> str:
        if num == 0:
            return "0"
        hex_chars = "0123456789abcdef"
        result = []
        # Handle negative numbers using two's complement
        num &= 0xFFFFFFFF
        while num:
            result.append(hex_chars[num % 16])
            num //= 16
        return ''.join(reversed(result))
      

class Solution {
public:
    string toHex(int num) {
        if (num == 0) return "0";
        string hex_chars = "0123456789abcdef";
        string result = "";
        unsigned int n = num;
        while (n) {
            result += hex_chars[n % 16];
            n /= 16;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};
      

class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] hexChars = "0123456789abcdef".toCharArray();
        StringBuilder sb = new StringBuilder();
        // Use unsigned right shift to handle negatives
        while (num != 0 && sb.length() < 8) {
            sb.append(hexChars[num & 0xf]);
            num >>>= 4;
        }
        return sb.reverse().toString();
    }
}
      

var toHex = function(num) {
    if (num === 0) return "0";
    let hexChars = "0123456789abcdef";
    let result = "";
    // Use 32-bit unsigned representation
    num = num >>> 0;
    while (num) {
        result = hexChars[num % 16] + result;
        num = Math.floor(num / 16);
    }
    return result;
};