algoadvance

Leetcode 405. Convert a Number to Hexadecimal

Problem Statement

The problem is to convert a given integer number to its hexadecimal representation. The hexadecimal numeral system is base-16, which uses sixteen symbols: 0-9 and a-f. For example, the hexadecimal representation of the decimal number 26 is “1a”.

You need to write a function toHex that takes an integer as input and returns a string representing its hexadecimal value.

Clarifying Questions

  1. Input Range: What is the range of the input integer value?
    • The input integer is a 32-bit signed integer.
  2. Negative Numbers: How should negative numbers be treated?
    • For negative numbers, the hexadecimal representation should use two’s complement.
  3. Leading Zeroes: Should we consider leading zeroes in the output?
    • No leading zeroes should be in the output unless the number is zero itself.

With these clarifications, we can proceed to the next section.

Strategy

  1. Handling Negatives: Since the input can be negative, we need to handle the two’s complement representation. For a 32-bit signed integer, this means treating negative numbers unsigned by masking with 0xFFFFFFFF.

  2. Hexadecimal Mapping: We need a map of digits to hexadecimal characters (0-9 to 0-9 and 10-15 to a-f).

  3. Conversion Process:

    • Use a loop to repeatedly take the last 4 bits of the number and map it to the corresponding hexadecimal.
    • Shift the number right by 4 bits and repeat until the number is zero.
    • Since the process generates the hexadecimal digits in reverse order, reverse the final string before returning.

Code

#include <string>

class Solution {
public:
    std::string toHex(int num) {
        if (num == 0) {
            return "0";
        }

        const char hexDigits[] = "0123456789abcdef";
        std::string hexStr;
        
        // Process the number using two's complement for negative numbers
        unsigned int n = static_cast<unsigned int>(num);
        
        while (n != 0) {
            int lastFourBits = n & 0xF;
            hexStr += hexDigits[lastFourBits];
            n >>= 4;
        }
        
        // The digits were added in reverse order
        std::reverse(hexStr.begin(), hexStr.end());
        
        return hexStr;
    }
};

Time Complexity

The time complexity of this solution is O(log(n)), where n is the absolute value of the input number. This is because the loop extracts 4 bits at a time and shifts the number right, effectively reducing it by a factor of 16 each iteration. For 32-bit integers, this loop will run at most 8 times (since 32/4 = 8).

This approach efficiently converts an integer to its hexadecimal representation, handling both positive and negative values correctly.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI