Jobs

Interviews

Discussions

Convert a Number to Hexadecimal

Easy

Asked by:

More companies

20 views

Topics:

Bit Manipulation

Given a 32-bit integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.

Example 1:

Input: num = 26
Output: "1a"

Example 2:

Input: num = -1
Output: "ffffffff"

Constraints:

-2³¹ <= num <= 2³¹ - 1

Try coding it in LeetCode

Convert a Number to Hexadecimal

Easy

Asked by:

20 views

Topics:

Bit Manipulation

Given a 32-bit integer num, return a string representing its hexadecimal representation. For negative integers, two’s complement method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

Note: You are not allowed to use any built-in library method to directly solve this problem.

Example 1:

Input: num = 26
Output: "1a"

Example 2:

Input: num = -1
Output: "ffffffff"

Constraints:

-2³¹ <= num <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer `num`? Is it limited to 32-bit integers?
What hexadecimal representation should I return for the integer 0? Should it be "0"?
Can I assume the hexadecimal representation will always fit within a reasonable string length, or are there any maximum length constraints?
Is the output hexadecimal string expected to be lowercase, uppercase, or can I choose?
By 'two's complement method', do you mean the standard representation, or are there specific requirements for how it should be handled?

Brute Force Solution

Approach

We need to change a regular number into its hexadecimal form. The brute force way means trying every single possibility. We will check the number piece by piece and convert each one individually.

Here's how the algorithm would work step-by-step:

First, handle the special case when the input number is zero; if so, the hexadecimal representation is simply zero.
Next, we need a way to convert a small number between 0 and 15 to its hexadecimal character (0-9, a-f). So, we will create a lookup table to quickly find the correct character for each value.
Now, repeatedly take the remainder when the number is divided by 16. This remainder corresponds to one hexadecimal digit.
Use the lookup table to convert this remainder to its hexadecimal character.
Add this character to the beginning of our hexadecimal representation string.
Then divide the original number by 16 and repeat the process until the original number becomes zero.
Finally, return the hexadecimal representation string we built up.

Code Implementation

def convert_to_hexadecimal(number):
    if number == 0:
        return "0"

    hexadecimal_characters = "0123456789abcdef"
    hexadecimal_representation = ""

    while number != 0:
        # Get the remainder for the hexadecimal digit
        remainder = number % 16

        # Convert the remainder to its hexadecimal character and add to result
        hexadecimal_character = hexadecimal_characters[remainder]
        hexadecimal_representation = hexadecimal_character + hexadecimal_representation

        # Integer divide to get the next set of digits
        number = number // 16

    return hexadecimal_representation

Big(O) Analysis

Time Complexity

O(1) – The algorithm converts an integer to its hexadecimal representation. The number of iterations in the while loop is determined by the number of hexadecimal digits required to represent the integer. Since the input is a 32-bit integer, the maximum number of hexadecimal digits is 8 (32 / 4 = 8). Therefore, the loop iterates at most 8 times, regardless of the input number's value. The operations inside the loop (modulo, division, lookup) take constant time. Thus, the overall time complexity is O(1).

Space Complexity

O(1) – The algorithm uses a lookup table of constant size (16 characters for hexadecimal digits), which does not depend on the input number. It also uses a string to store the hexadecimal representation and the remainder from the division. The size of the hexadecimal string is proportional to the number of hexadecimal digits needed to represent the input number, but since integers have a fixed size (e.g., 32 or 64 bits), the maximum number of hexadecimal digits is also fixed. Therefore, the auxiliary space used is constant, regardless of the input number.

Optimal Solution

Approach

The trick is to work directly with the number's bits to build the hexadecimal representation piece by piece. We look at the number in chunks of four bits at a time and convert each chunk to its hexadecimal equivalent.

Here's how the algorithm would work step-by-step:

Handle the special case where the input is zero; the hexadecimal representation is simply '0'.
If the number is negative, treat it as an unsigned 32-bit integer. This effectively handles the two's complement representation.
Process the number four bits at a time, starting from the least significant bits.
For each group of four bits, convert it to its hexadecimal digit (0-9 or a-f).
Append this hexadecimal digit to the beginning of the result string.
Right-shift the original number by four bits to move to the next group of four bits.
Repeat the process until the number becomes zero.

Code Implementation

def convert_to_hexadecimal(number):
    if number == 0:
        return '0'

    hexadecimal_characters = '0123456789abcdef'
    result = ''

    # Treat negative numbers as unsigned 32-bit integers
    unsigned_number = number & 0xFFFFFFFF

    while unsigned_number > 0:
        # Get the last four bits of the number
        four_bits = unsigned_number & 0xF

        # Convert the four bits to a hexadecimal character
        hexadecimal_digit = hexadecimal_characters[four_bits]

        # Prepend the hexadecimal digit to the result
        result = hexadecimal_digit + result

        # Right shift the number by four bits
        unsigned_number >>= 4

    return result

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates a fixed number of times, determined by the size of the input integer (32 bits). Since we are treating the input as an unsigned 32-bit integer, the loop runs at most 8 times (32 bits / 4 bits per hexadecimal digit). The number of iterations is independent of the input number's magnitude. Therefore, the time complexity is constant, or O(1).

Space Complexity

O(1) – The algorithm utilizes a string to store the hexadecimal representation. In the worst-case scenario, a 32-bit integer (N=32) requires 8 hexadecimal digits (32 bits / 4 bits per hex digit = 8 digits), plus perhaps a constant amount of space for a temporary variable to store the hex digit while building the result string. Thus, the extra space scales with the number of hexadecimal digits, which is constant and does not depend on the magnitude of the input beyond its bit-length. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input is 0	Return '0' directly as the hexadecimal representation of 0 is '0'.
Input is the minimum integer value (Integer.MIN_VALUE)	Handles the two's complement representation correctly; ensures the hexadecimal conversion doesn't cause an integer overflow.
Input is a positive integer close to the maximum integer value (Integer.MAX_VALUE)	Ensures the conversion process does not result in exceeding representation bounds.
Input is a negative integer close to 0 (-1)	Handles the two's complement representation close to zero correctly; should return 'ffffffff'.
Large positive integers that, when converted to hex, have leading zeros that need to be removed.	Ensure removal of leading zeros after conversion, until a non-zero digit or a single zero remains.
Negative number where the most significant hex digit is 7 (e.g., 0x7FFFFFFF representing a smaller negative number)	The two's complement ensures the correct sign extension and hexadecimal representation.
Inputs causing bitwise operations (specifically right shifts) to result in unexpected behavior related to sign extension	Using unsigned right shift (>>> in Java) prevents sign extension issues during the conversion process.
Repeated calls to the function with different values, including edge cases	The function should correctly convert each independent value without side effects from previous calls.

Input is 0

How to Handle:

Return '0' directly as the hexadecimal representation of 0 is '0'.

Input is the minimum integer value (Integer.MIN_VALUE)

How to Handle:

Handles the two's complement representation correctly; ensures the hexadecimal conversion doesn't cause an integer overflow.

Input is a positive integer close to the maximum integer value (Integer.MAX_VALUE)

How to Handle:

Ensures the conversion process does not result in exceeding representation bounds.

Input is a negative integer close to 0 (-1)

How to Handle:

Handles the two's complement representation close to zero correctly; should return 'ffffffff'.

Large positive integers that, when converted to hex, have leading zeros that need to be removed.

How to Handle:

Ensure removal of leading zeros after conversion, until a non-zero digit or a single zero remains.

Negative number where the most significant hex digit is 7 (e.g., 0x7FFFFFFF representing a smaller negative number)

How to Handle:

The two's complement ensures the correct sign extension and hexadecimal representation.

Inputs causing bitwise operations (specifically right shifts) to result in unexpected behavior related to sign extension

How to Handle:

Using unsigned right shift (>>> in Java) prevents sign extension issues during the conversion process.

Repeated calls to the function with different values, including edge cases

How to Handle:

The function should correctly convert each independent value without side effects from previous calls.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for the input integer `num`? Is it limited to 32-bit integers?
What hexadecimal representation should I return for the integer 0? Should it be "0"?
Can I assume the hexadecimal representation will always fit within a reasonable string length, or are there any maximum length constraints?
Is the output hexadecimal string expected to be lowercase, uppercase, or can I choose?
By 'two's complement method', do you mean the standard representation, or are there specific requirements for how it should be handled?

Brute Force Solution

Approach

We need to change a regular number into its hexadecimal form. The brute force way means trying every single possibility. We will check the number piece by piece and convert each one individually.

Here's how the algorithm would work step-by-step:

First, handle the special case when the input number is zero; if so, the hexadecimal representation is simply zero.
Next, we need a way to convert a small number between 0 and 15 to its hexadecimal character (0-9, a-f). So, we will create a lookup table to quickly find the correct character for each value.
Now, repeatedly take the remainder when the number is divided by 16. This remainder corresponds to one hexadecimal digit.
Use the lookup table to convert this remainder to its hexadecimal character.
Add this character to the beginning of our hexadecimal representation string.
Then divide the original number by 16 and repeat the process until the original number becomes zero.
Finally, return the hexadecimal representation string we built up.

Code Implementation

def convert_to_hexadecimal(number):
    if number == 0:
        return "0"

    hexadecimal_characters = "0123456789abcdef"
    hexadecimal_representation = ""

    while number != 0:
        # Get the remainder for the hexadecimal digit
        remainder = number % 16

        # Convert the remainder to its hexadecimal character and add to result
        hexadecimal_character = hexadecimal_characters[remainder]
        hexadecimal_representation = hexadecimal_character + hexadecimal_representation

        # Integer divide to get the next set of digits
        number = number // 16

    return hexadecimal_representation

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Handle the special case where the input is zero; the hexadecimal representation is simply '0'.
If the number is negative, treat it as an unsigned 32-bit integer. This effectively handles the two's complement representation.
Process the number four bits at a time, starting from the least significant bits.
For each group of four bits, convert it to its hexadecimal digit (0-9 or a-f).
Append this hexadecimal digit to the beginning of the result string.
Right-shift the original number by four bits to move to the next group of four bits.
Repeat the process until the number becomes zero.

Code Implementation

def convert_to_hexadecimal(number):
    if number == 0:
        return '0'

    hexadecimal_characters = '0123456789abcdef'
    result = ''

    # Treat negative numbers as unsigned 32-bit integers
    unsigned_number = number & 0xFFFFFFFF

    while unsigned_number > 0:
        # Get the last four bits of the number
        four_bits = unsigned_number & 0xF

        # Convert the four bits to a hexadecimal character
        hexadecimal_digit = hexadecimal_characters[four_bits]

        # Prepend the hexadecimal digit to the result
        result = hexadecimal_digit + result

        # Right shift the number by four bits
        unsigned_number >>= 4

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	Return '0' directly as the hexadecimal representation of 0 is '0'.
Input is the minimum integer value (Integer.MIN_VALUE)	Handles the two's complement representation correctly; ensures the hexadecimal conversion doesn't cause an integer overflow.
Input is a positive integer close to the maximum integer value (Integer.MAX_VALUE)	Ensures the conversion process does not result in exceeding representation bounds.
Input is a negative integer close to 0 (-1)	Handles the two's complement representation close to zero correctly; should return 'ffffffff'.
Large positive integers that, when converted to hex, have leading zeros that need to be removed.	Ensure removal of leading zeros after conversion, until a non-zero digit or a single zero remains.
Negative number where the most significant hex digit is 7 (e.g., 0x7FFFFFFF representing a smaller negative number)	The two's complement ensures the correct sign extension and hexadecimal representation.
Inputs causing bitwise operations (specifically right shifts) to result in unexpected behavior related to sign extension	Using unsigned right shift (>>> in Java) prevents sign extension issues during the conversion process.
Repeated calls to the function with different values, including edge cases	The function should correctly convert each independent value without side effects from previous calls.

Input is 0

How to Handle:

Return '0' directly as the hexadecimal representation of 0 is '0'.

Input is the minimum integer value (Integer.MIN_VALUE)

How to Handle:

Handles the two's complement representation correctly; ensures the hexadecimal conversion doesn't cause an integer overflow.

Input is a positive integer close to the maximum integer value (Integer.MAX_VALUE)

How to Handle:

Ensures the conversion process does not result in exceeding representation bounds.

Input is a negative integer close to 0 (-1)

How to Handle:

Handles the two's complement representation close to zero correctly; should return 'ffffffff'.

Large positive integers that, when converted to hex, have leading zeros that need to be removed.

How to Handle:

Ensure removal of leading zeros after conversion, until a non-zero digit or a single zero remains.

Negative number where the most significant hex digit is 7 (e.g., 0x7FFFFFFF representing a smaller negative number)

How to Handle:

The two's complement ensures the correct sign extension and hexadecimal representation.

Inputs causing bitwise operations (specifically right shifts) to result in unexpected behavior related to sign extension

How to Handle:

Using unsigned right shift (>>> in Java) prevents sign extension issues during the conversion process.

Repeated calls to the function with different values, including edge cases

How to Handle:

The function should correctly convert each independent value without side effects from previous calls.