LeetCode 405 - Convert a Number to Hexadecimal

Difficulty: 🟢 Easy
Topics: Math, String, Bit Manipulation

Solution

Problem Understanding

The problem asks us to convert a given 32-bit integer num into its hexadecimal representation as a string. Hexadecimal, or base-16, uses digits 0-9 and letters a-f to represent values 0-15. For positive numbers, the conversion is straightforward: repeatedly divide the number by 16 and map remainders to the hexadecimal digits. For negative numbers, the problem explicitly specifies using two's complement, which means representing the number as if it were stored in 32 bits. For example, -1 becomes 0xffffffff because two's complement represents -1 as all bits set to 1 in a 32-bit integer.

The input range is from -2^31 to 2^31 - 1. This guarantees the input is a standard 32-bit signed integer, so we do not need to handle arbitrary large integers.

Important edge cases include 0, which should return "0" without leading zeros, and negative numbers, which require proper masking to convert to a 32-bit two's complement hexadecimal. Handling numbers like -1 or -2^31 incorrectly by naive division could result in errors, so a bitwise approach is more reliable.

Approaches

Brute-Force Approach

A naive approach would involve repeatedly dividing the integer by 16 and constructing the hexadecimal string from the remainders. For negative numbers, a straightforward division loop may fail because Python or Go handle negative division differently, and we would need to manually compute the two's complement representation. This approach is cumbersome and error-prone, especially for negatives, because we would have to simulate a 32-bit integer manually.

Optimal Approach

The key insight for an optimal solution is to use bit manipulation. For a 32-bit number, we can repeatedly extract the last 4 bits using a bitwise AND with 0xf, then shift the number right by 4 bits. This works consistently for positive and negative numbers because we can mask the number with 0xffffffff to simulate a 32-bit unsigned integer. This avoids handling negative numbers separately and produces the correct hexadecimal string in lowercase.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(log(num))	O(log(num))	Repeated division, manual two's complement for negatives
Optimal	O(1)	O(1)	Bitwise approach handles both positive and negative numbers in constant 32-bit iterations

Algorithm Walkthrough

Handle zero: If num is zero, immediately return "0". This handles the special case with no loops.
Mask negative numbers: Use num & 0xffffffff to ensure we treat the number as an unsigned 32-bit integer. This converts negatives to their two's complement representation.
Prepare hexadecimal digits: Create a string hex_chars = "0123456789abcdef" to map values 0-15 to hexadecimal characters.
Build the hexadecimal string: Initialize an empty string res. While num is not zero, extract the last 4 bits with num & 0xf, map it to the corresponding hex character, prepend it to res, and right-shift num by 4 bits.
Return result: Once all bits are processed, res contains the correct hexadecimal string.

Why it works: Each iteration extracts exactly one hexadecimal digit starting from the least significant digit. Masking ensures the negative numbers are represented in 32-bit two's complement form. Since a 32-bit integer has at most 8 hexadecimal digits, the loop iterates at most 8 times, guaranteeing correctness and efficiency.

Python Solution

class Solution:
    def toHex(self, num: int) -> str:
        if num == 0:
            return "0"
        
        hex_chars = "0123456789abcdef"
        res = ""
        num &= 0xffffffff  # mask to 32-bit unsigned
        
        while num:
            res = hex_chars[num & 0xf] + res
            num >>= 4
        
        return res

This implementation first checks for zero, then masks the number to handle negatives. The loop iteratively extracts each 4-bit chunk and builds the hexadecimal string. Using string concatenation in front ensures the order of digits is correct without needing a reverse at the end.

Go Solution

func toHex(num int) string {
    if num == 0 {
        return "0"
    }

    hexChars := "0123456789abcdef"
    res := ""
    n := uint32(num) // cast to 32-bit unsigned integer
    
    for n != 0 {
        res = string(hexChars[n&0xf]) + res
        n >>= 4
    }

    return res
}

In Go, we use a type cast to uint32 to handle negative numbers correctly, since Go does not have Python-style arbitrary integer handling. The rest of the logic mirrors the Python approach.

Worked Examples

Example 1: num = 26

Step	num (decimal)	num & 0xf	Hex char	res
1	26	10	"a"	"a"
2	1	1	"1"	"1a"

Result: "1a"

Example 2: num = -1

Step	num (hex 32-bit)	num & 0xf	Hex char	res
1	0xffffffff	15	"f"	"f"
2	0xfffffff	15	"f"	"ff"
3	0xffffff	15	"f"	"fff"
4	0xfffff	15	"f"	"ffff"
5	0xffff	15	"f"	"fffff"
6	0xfff	15	"f"	"ffffff"
7	0xff	15	"f"	"fffffff"
8	0xf	15	"f"	"ffffffff"

Result: "ffffffff"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	The loop runs at most 8 iterations for a 32-bit number
Space	O(1)	The output string has at most 8 characters; constant space used for hex digits

Since 32-bit numbers are fixed, this approach has effectively constant time and space complexity.

Test Cases

# Provided examples
assert Solution().toHex(26) == "1a"  # simple positive number
assert Solution().toHex(-1) == "ffffffff"  # negative number, two's complement

# Boundary cases
assert Solution().toHex(0) == "0"  # zero edge case
assert Solution().toHex(15) == "f"  # single hex digit
assert Solution().toHex(16) == "10"  # rollover to next hex digit
assert Solution().toHex(-2147483648) == "80000000"  # min 32-bit int
assert Solution().toHex(2147483647) == "7fffffff"  # max 32-bit int

# Random case
assert Solution().toHex(305419896) == "12345678"  # arbitrary number

Test	Why
26	simple positive number conversion
-1	negative number, check two's complement handling
0	zero edge case
15	single digit hexadecimal
16	transition from single to double hex digit
-2147483648	min 32-bit integer
2147483647	max 32-bit integer
305419896	arbitrary number, general correctness

Edge Cases

One important edge case is 0, which should return "0" without any additional zeros. Without a special check, the loop would return an empty string.

Another edge case is negative numbers, especially -1 or -2147483648. Naive division can give wrong results due to how negative division works in Python or Go, so masking with 0xffffffff ensures a proper 32-bit two's complement representation.

A third edge case is numbers that align exactly at hexadecimal boundaries, such as 15, 16, 255, or 256. These test whether the conversion correctly rolls over from one hex digit to the next without missing or duplicating digits.

This solution correctly handles all three categories by masking negatives, checking zero explicitly, and iteratively processing 4-bit chunks.