## 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

- If the number is 0, return “0” as the hexadecimal representation.
- Create a string of hexadecimal characters, hex_chars = “0123456789abcdef”.
- Initialize an empty string
`result`

to store the hexadecimal representation. - Loop until
`num`

is not equal to 0. - 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`

. - Right shift
`num`

by 4 positions to process the next set of 4 bits. - 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.