algoadvance

Leetcode 405. Convert a Number to Hexadecimal

Problem Statement

You need to write a function that converts a given integer to its hexadecimal representation. For the purpose of this problem, assume that all integers are signed 32-bit integers, and you are not allowed to use any built-in libraries to directly solve this problem.

Clarifying Questions

  1. Q: Can the input number be negative?
    • A: Yes, the input number can be negative as it is a signed 32-bit integer.
  2. Q: How should negative numbers be handled in the hexadecimal representation?
    • A: For negative numbers, you should use two’s complement notation.

Strategy

  1. Handle Edge Cases:
    • If num is 0, simply return “0”.
    • Since the problem specifies a 32-bit signed integer, special consideration is required for numbers that are negative.
  2. Two’s Complement for Negative Numbers:
    • The two’s complement of a negative number x is calculated by 2^32 + x.
  3. Conversion to Hexadecimal:
    • Use a loop to continuously extract the last 4 bits from the number and map these to their corresponding hexadecimal character.
    • Use bit manipulation to shift the number and extract bits.

Code

Here is the implementation of the solution:

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

        char[] hexChars = "0123456789abcdef".toCharArray();
        StringBuilder hexString = new StringBuilder();

        // we are only interested in the last 32 bits of num
        while (num != 0 && hexString.length() < 8) {
            int currentHexDigit = num & 0xf; // Extract the last 4 bits
            hexString.append(hexChars[currentHexDigit]);
            num >>>= 4; // Logical right shift by 4 bits
        }

        return hexString.reverse().toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // Test cases
        System.out.println(sol.toHex(26)); // Expected "1a"
        System.out.println(sol.toHex(-1)); // Expected "ffffffff"
    }
}

Explanation

  1. Edge Case Handling: We check if num is 0 and return “0” immediately.
  2. Hex Characters: We define a character array holding all hexadecimal characters.
  3. Hex Conversion Loop:
    • We use a loop to repeatedly extract the last 4 bits of the number using num & 0xf.
    • Append the corresponding hexadecimal character to a StringBuilder.
    • Perform a logical right shift (>>>) to remove the last 4 bits.
    • Repeat until the number becomes 0 or we have processed 8 characters (handling the limitation of a 32-bit number).
  4. Reverse and Return: The StringBuilder contents are reversed at the end because we constructed the hex string from least significant to most significant digit.

Time Complexity

The time complexity of this conversion is O(1), because the loop iterates at most 8 times (since a 32-bit number can be represented by at most 8 hexadecimal digits). Thus, the computation does not depend on the size or value of the input integer.

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