405. Convert a Number to Hexadecimal

Description

The problem is to convert a given integer into its hexadecimal representation. The integer can be positive or negative. For negative numbers, the function should treat them as unsigned integers in the range of 32-bit numbers. The function must return a string representing the hexadecimal value, without the "0x" prefix, and it should work for both negative and positive numbers.

Intuition

Hexadecimal numbers use base 16, represented by the digits 0-9 and the letters a-f. For non-negative numbers, repeatedly dividing the number by 16 and storing the remainders gives the hexadecimal representation. For negative numbers, we can use the unsigned 32-bit representation, effectively adding 2^32 to handle negative numbers.

Approach

1. Define a string or list containing the hexadecimal digits 0-9 and a-f.
2. If the number is 0, return "0" directly.
3. If the number is negative, convert it to its 32-bit unsigned equivalent by adding 2^32 to the number.
4. Continuously divide the number by 16 and store the remainder at each step, which corresponds to the hexadecimal digit.
5. Stop when the number becomes 0.
6. Finally, combine the digits and return the hexadecimal string.

Complexity

Time Complexity:

O(log n) where n is the input number. This is because we are repeatedly dividing the number by 16.

Space Complexity:

O(log n), as we store the digits of the hexadecimal number in a string or list.

Code

C++

class Solution {
public:
    string toHex(int num) {
        string hexas = "0123456789abcdef";
        
        if (num == 0) return "0";
        if (num > 0 && num <= 15) return string(1, hexas[num]);
        
        unsigned int n = num;
        string result = "";
        
        while (n > 0) {
            result = hexas[n % 16] + result;
            n /= 16;
        }
        
        return result;
    }
};

Python

class Solution:
    def toHex(self, num: int) -> str:
        hexas = "0123456789abcdef"
        
        if num == 0:
            return "0"
        if num > 0 and num <= 15:
            return hexas[num]
        
        if num < 0:
            num += 2**32
        
        result = []
        
        while num > 0:
            result.append(hexas[num % 16])
            num //= 16
        
        return ''.join(result[::-1])

Java

class Solution {
    public String toHex(int num) {
        char[] hexas = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        
        if (num == 0) return "0";
        if (num > 0 && num <= 15) return Character.toString(hexas[num]);

        long n = num;  // handle negative values
        if (n < 0) n += (1L << 32);
        
        StringBuilder result = new StringBuilder();
        
        while (n > 0) {
            result.insert(0, hexas[(int)(n % 16)]);
            n /= 16;
        }
        
        return result.toString();
    }
}

JavaScript

var toHex = function (num) {

    const hexas = {
        0: 0, 6: 6, 10: "a",
        1: 1, 7: 7, 11: "b",
        2: 2, 8: 8, 12: "c",
        3: 3, 9: 9, 13: "d",
        4: 4, 14: "e",
        5: 5, 15: "f"
    }
    if (num >= 0 && num <= 15) return hexas[num].toString();
    if (num < 0) num = num >>> 0;

    let newArr = [];
    while (num >= 16) {

        let rest = (num % 16);

        newArr.unshift(hexas[rest]);

        num = Math.floor(num / 16);
    }
    newArr.unshift(hexas[num]);

    return newArr.join("");
};