405. Convert a Number to Hexadecimal

EasyBit ManipulationMath

Problem Description

The LeetCode problem requires us to convert an integer to its hexadecimal representation. The process should work for both positive and negative integers. When dealing with the hexadecimal system, instead of using the decimal digits 0-9, we also use the letters 'a' to 'f' to represent the values 10 to 15. For negative integers, the standard method of conversion is using the two's complement representation.

Here are key points to consider:

The output should be a string.
Each hexadecimal character is a representation of 4 bits.
The letters in the output should all be lowercase.
The output should not have any leading zeroes unless the number is '0'.
Built-in library methods for direct conversion are not allowed, implying that the solution should manually perform the conversion.

Intuition

The solution uses bitwise operations and direct character mapping to convert an integer to its hexadecimal equivalent.

Here's the reasoning behind the solution:

Since we cannot use built-in library methods, we create a string chars containing hexadecimal characters '0' to 'f' which map to their corresponding decimal values from 0 to 15.
The given number is processed from its most significant hex digit to its least significant digit, checking 4 bits at a time (which corresponds to a single hex digit). This is achieved by using bitwise operations:
- The right-shift operation (>>) is used to bring the set of 4 bits we want to convert into the least significant position.
- The bitwise AND operation (&) with 0xF (which is 1111 in binary) is used to isolate these 4 bits.
For each set of 4 bits, we look up the corresponding hexadecimal digit from our predefined string chars and add it into an array s.
We use a flag (s or x != 0) to avoid adding leading zeros to our result array s. This way, zero(es) will be appended only if there are non-zero digits already in the array, or the current digit is itself non-zero.
Since we're going from most significant hex digit to least significant, we don't need to reverse the array s at the end, we simply join it to form the result string.

The core of the solution hinges on the concept that a hexadecimal number is just a representation of a binary number with a grouping of 4 bits at a time and that two's complement binary representation for negative numbers will automatically handle the sign.

Learn more about Math patterns.

Solution Approach

The implementation of the solution uses bit manipulation, which is a powerful technique in computer programming for tasks involving low-level data processing. Bit manipulation operations are used to perform operations directly on the binary digits or bits of a number. In the case of converting an integer to its hexadecimal representation, we particularly use bitwise shifting and bitwise AND operations.

Here's a step-by-step breakdown of how the solution approach works:

Special Case for Zero: The function begins by checking if num is zero. If it is, the function immediately returns '0' since, in hexadecimal, 0 is represented as 0.
Character Mapping for Hexadecimal Digits: A string chars, which contains all the hexadecimal digits from 0 to 9 and a to f, is used as a map. This is the data structure used for converting a 4-bit binary number to its hexadecimal character.
Array Initialization: An empty list s is initialized to accumulate the resulting hexadecimal characters. This list will act as a stack to hold the characters before joining them into a final string.
Iterating Over Each Hex Digit: The main for-loop processes the integer 4 bits at a time, which corresponds to one hex digit. The loop iterates 8 times since an integer in most systems is 32 bits and 32/4 = 8 hex digits. The range in the loop, range(7, -1, -1), indicates the iteration goes from the most significant hex digit to the least significant.
Extracting Hex Digits Using Bit Manipulation:
- Bitwise Right Shift: The number num is right-shifted 4 * i times, bringing the current hex digit to the least significant position.
- Bitwise AND with 0xF: The operation (num >> (4 * i)) & 0xF then isolates these 4 bits.
Avoiding Leading Zeros: To avoid leading zeros in the output, there is a check to see if the list s is empty or if the current hex digit x is non-zero before appending the character to the s list. This way, we are sure that the final string will not contain unnecessary leading zeros.
Appending to the Result List: Once the correct hex digit is determined, it is appended to the list s.
Building the Result String: After the loop finishes processing all hex digits, the list s is joined (''.join(s)) to form the hexadecimal string, which is then returned as the result.

The solution makes judicious use of bit manipulation to convert each group of 4 bits into its hexadecimal character equivalent without ever processing the entire number as a whole. This localized processing is ideal for handling large integers and ensures compatibility with the two's complement representation for negative integers.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to understand how the solution approach works. Consider the decimal number 26 as our example, which needs to be converted into a hexadecimal string.

Following our step-by-step solution:

Special Case for Zero: First, we check if the number is zero. In our case, 26 is not zero, so we can proceed to the next steps.
Character Mapping for Hexadecimal Digits: We have a string chars = '0123456789abcdef', which helps us map each 4-bit binary number to its hex character.
Array Initialization: We initialize an empty list s = [] that will hold each hex character before we join them.
Iterating Over Each Hex Digit: The for loop will iterate 8 times since a 32-bit integer has 8 hex digits. But for simplicity (our number is small), we only need to consider iterations that don't lead to a 0 result from (num >> (4 * i)) & 0xF. This means for our example, 26, we only need the last two iterations, i=1 and i=0.
Extracting Hex Digits Using Bit Manipulation:
- For i=1:
  - Right shift 26 by 4 * 1 = 4: 26 >> 4 gives 1.
  - Bitwise AND with 0xF: (1) & 0xF results in 1.
- Since s is empty and 1 is non-zero, we should append its hex character to s. So, we look up 1 in chars, which gives us '1', and we append it: s += ['1'].
- For i=0:
  - Right shift 26 by 4 * 0 = 0: 26 >> 0 gives 26.
  - Bitwise AND with 0xF: (26) & 0xF results in 10 (since binary 26 is 11010 and 1010 is 10 in decimal).
- Since 10 is non-zero and s is not empty, we look up 10 in chars, yielding 'a'. Append it to s: s += ['a'].
Avoiding Leading Zeros: As explained in the steps, we only appended characters since we did not encounter a situation where a zero would be a leading character.
Appending to the Result List: At this point, we have s = ['1', 'a'].
Building the Result String: Lastly, we join the list into a string, resulting in '1a', which is the hexadecimal representation of 26.

Upon running this process on the given number 26, we've successfully converted it to its hexadecimal representation '1a' using the explained bit manipulation technique.

Solution Implementation

1class Solution:
2    def toHex(self, num: int) -> str:
3        # If the number is 0, return '0' directly
4        if num == 0:
5            return '0'
6      
7        # String containing hexadecimal characters for conversion
8        hex_chars = '0123456789abcdef'
9      
10        # List to store hexadecimal characters
11        hex_string = []
12      
13        # We extract 4 bits at a time from the integer, and we process from the MSB to the LSB
14        # On a 32-bit architecture, we process the integer as 8 groups of 4 bits.
15        for i in range(7, -1, -1):
16            # Extract 4 bits by shifting right (4 * position) and masking with 0xF to get the value
17            current_bits = (num >> (4 * i)) & 0xF
18          
19            # If the hex_string list is non-empty or the current_bits are non-zero, append the corresponding hex character
20            # This check also prevents leading zeros from being included in the output
21            if hex_string or current_bits != 0:
22                hex_string.append(hex_chars[current_bits])
23      
24        # Join the list into a string and return it as the hexadecimal representation
25        return ''.join(hex_string)
26

1public class Solution {
2  
3    // Method to convert a given integer to a hexadecimal string
4    public String toHex(int num) {
5
6        // If the number is zero, then the hexadecimal string is simply "0"
7        if (num == 0) {
8            return "0";
9        }
10
11        // StringBuilder to build the hexadecimal string
12        StringBuilder hexBuilder = new StringBuilder();
13
14        // Loop to process the number until all hexadecimal digits are obtained
15        while (num != 0) {
16
17            // Extract the last 4 bits of the number
18            int last4Bits = num & 15; // 15 in hexadecimal is 0xF
19          
20            // If the value of last 4 bits is less than 10, append the corresponding decimal value as character
21            if (last4Bits < 10) {
22                hexBuilder.append(last4Bits);
23            } else {
24                // If the value is 10 or above, convert it to a hexadecimal character from 'a' to 'f'
25                hexBuilder.append((char) (last4Bits - 10 + 'a'));
26            }
27
28            // Shift the number 4 bits to the right to process the next hexadecimal digit
29            // Using the unsigned right shift operator ">>>" to handle negative numbers
30            num >>>= 4;
31        }
32
33        // Reverse the StringBuilder contents to get the right hexadecimal string order and return it
34        return hexBuilder.reverse().toString();
35    }
36}
37

1class Solution {
2public:
3    string toHex(int num) {
4        // Check base condition: if num is 0, return "0"
5        if (num == 0) {
6            return "0";
7        }
8
9        // Initialize the output string
10        string hexString = "";
11
12        // Iterate over each hex digit from the most significant to least significant
13        for (int i = 7; i >= 0; --i) {
14            // Extract current hex digit from the number
15            int hexDigit = (num >> (4 * i)) & 0xf;
16
17            // Skip leading zeros
18            if (hexString.size() > 0 || hexDigit != 0) {
19                // Convert the current digit to its hex char representation
20                char hexChar = hexDigit < 10 ? (char)(hexDigit + '0') : (char)(hexDigit - 10 + 'a');
21                // Append the hex character to the hex string
22                hexString += hexChar;
23            }
24        }
25
26        // Return the complete hex string
27        return hexString;
28    }
29};
30

1function toHex(num: number): string {
2    // Check base condition: if num is 0, return "0"
3    if (num === 0) {
4        return "0";
5    }
6
7    // Initialize the output string
8    let hexString = "";
9
10    // Iterate over each hex digit from the most significant to least significant
11    for (let i = 7; i >= 0; i--) {
12        // Extract current hex digit from the number
13        const hexDigit = (num >> (4 * i)) & 0xf;
14
15        // Skip leading zeros
16        if (hexString.length > 0 || hexDigit !== 0) {
17            // Convert the current digit to its hex char representation
18            const hexChar = hexDigit < 10 ? String.fromCharCode(hexDigit + '0'.charCodeAt(0)) : 
19                                            String.fromCharCode(hexDigit - 10 + 'a'.charCodeAt(0));
20            // Append the hex character to the hex string
21            hexString += hexChar;
22        }
23    }
24
25    // Return the complete hex string
26    return hexString;
27}
28

Time and Space Complexity

Time Complexity

The given code performs a fixed number of iterations regardless of the size of the input num since it iterates 8 times corresponding to each hex digit of a 32-bit integer. The shift operation >> and the bitwise AND operation & take constant time, and the append operation for a Python list also takes constant time on average. Therefore, the time complexity is O(1).

Space Complexity

The space complexity is determined by the additional space used by the algorithm. Here, the space is used to store the hex characters in the chars string and the s list which is used to build the final hex string. The chars string is of a fixed size, and the s list grows to a maximum length of 8 since a 32-bit integer can have at most 8 hex digits. Therefore, the space required does not depend on the input number, and the space complexity is also O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know