405. Convert a Number to Hexadecimal
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 (
&
) with0xF
(which is1111
in binary) is used to isolate these 4 bits.
- The right-shift operation (
-
For each set of 4 bits, we look up the corresponding hexadecimal digit from our predefined string
chars
and add it into an arrays
. -
We use a flag (
s
orx != 0
) to avoid adding leading zeros to our result arrays
. 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 as0
. -
Character Mapping for Hexadecimal Digits: A string
chars
, which contains all the hexadecimal digits from0
to9
anda
tof
, 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-shifted4 * 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.
- Bitwise Right Shift: The number
-
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 digitx
is non-zero before appending the character to thes
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 EvaluatorExample 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 a0
result from(num >> (4 * i)) & 0xF
. This means for our example,26
, we only need the last two iterations,i=1
andi=0
. -
Extracting Hex Digits Using Bit Manipulation:
-
For
i=1
:- Right shift
26
by4 * 1 = 4
:26 >> 4
gives1
. - Bitwise AND with
0xF
:(1) & 0xF
results in1
.
- Right shift
-
Since
s
is empty and1
is non-zero, we should append its hex character tos
. So, we look up1
inchars
, which gives us'1'
, and we append it:s += ['1']
. -
For
i=0
:- Right shift
26
by4 * 0 = 0
:26 >> 0
gives26
. - Bitwise AND with
0xF
:(26) & 0xF
results in10
(since binary 26 is11010
and1010
is10
in decimal).
- Right shift
-
Since
10
is non-zero ands
is not empty, we look up10
inchars
, yielding'a'
. Append it tos
: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 of26
.
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.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.