Leetcode – Convert a Number to Hexadecimal Solution in Python

Spread the love

Introduction

One of the problems on Leetcode that deals with bit manipulation and number representation is ‘Convert a Number to Hexadecimal’. In this comprehensive article, we will delve into different approaches to solve this problem in Python, analyze the time complexity, and understand the underlying concepts involved.

Problem Statement

The ‘Convert a Number to Hexadecimal’ problem is listed as problem number 405 on Leetcode. The problem statement is as follows:

Given an 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.

Example:

Input: num = 26
Output: "1a"

Note:

  • -2^31 <= num <= 2^31 – 1

Approach 1: Using Bit Manipulation

  1. If the number is 0, return “0” as the hexadecimal representation.
  2. Create a string of hexadecimal characters, hex_chars = “0123456789abcdef”.
  3. Initialize an empty string result to store the hexadecimal representation.
  4. Loop until num is not equal to 0.
  5. For each iteration, AND num with 15 (0xf in hexadecimal or 1111 in binary) to get the last four bits, use this as an index to get the hexadecimal character from hex_chars, and append it to result.
  6. Right shift num by 4 positions to process the next set of 4 bits.
  7. Reverse the string result and return it.
def toHex(num):
    if num == 0:
        return "0"
    
    hex_chars = "0123456789abcdef"
    result = ""
    
    # Loop until all bits are processed or num becomes 0
    for _ in range(8):
        # Get the last four bits
        result += hex_chars[num & 0xf]
        # Right shift the number by 4 bits
        num >>= 4
        # If num becomes 0, we break
        if num == 0:
            break
    
    # The result is constructed in reverse
    return result[::-1]

Time Complexity

The time complexity of this approach is O(1) because the loop runs a constant number of times (8), regardless of the value of num.

Approach 2: Using Python’s Built-in Function

Python provides a built-in function hex that can convert an integer into a hexadecimal string. However, for negative numbers, it prefixes the result with “-0x”. We need to handle this case separately.

def toHex(num):
    hex_str = hex(num)
    
    # Handle negative numbers
    if num < 0:
        # Strip "-0x" prefix and keep only last 8 characters
        return hex_str[3:].zfill(8)
    
    # Strip "0x" prefix
    return hex_str[2:]

Time Complexity

The time complexity of this approach is O(1), as Python’s built-in hex function runs in constant time.

Conclusion

The ‘Convert a Number to Hexadecimal’ problem on Leetcode challenges us to understand bit manipulation and number representation. The problem can be efficiently solved using bit manipulation, where we process the bits four at a time, which corresponds to a single hexadecimal character. An alternative approach involves using Python’s built-in function, hex, with some additional handling for negative numbers. Both approaches are efficient, with a constant time complexity. Understanding the details of bit manipulation can be especially helpful for problems dealing with low-level representation of numbers and bitwise operations.

Leave a Reply