Convert a Number to Hexadecimal

This problem involves the conversion of decimal to hexadecimal. Here’s a simple method that does this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def toHex(self, num: int) -> str:
        if num == 0:
            return "0"
        mp = "0123456789abcdef"  # mapping from decimal to hex
        result = ""
        for _ in range(8):  # as 8 hex numbers can represent any 32-bit number
            result = mp[num & 15] + result  # num & 15 gives the last 4 binary digits of num
            num = num >> 4  # right shift num by 4 to process next 4 binary digits
            if num == 0:
                break
        return result

In this solution, we first handle the special case where num is 0. Then we prepare a mapping string for decimal to hexadecimal conversion.

Next, we perform bitwise operations on num and append the hexadecimal digit to result for each iteration. Specifically, we:

  1. Use the bitwise AND operation (num & 15) to get the last 4 binary digits of num (equivalent to num mod 16), which is a decimal number in [0, 15]. We map it to the corresponding hexadecimal digit using the mapping string.

  2. Right shift num by 4 bits (num >> 4) to process the next 4 binary digits (or the next hexadecimal digit) in the next iteration.

We repeat the process until num becomes 0 or we have processed 8 hexadecimal digits (32 bits), whichever comes first.

In the bitwise AND operation, 15 is 1111 in binary. This operation masks the higher bits of num and keeps the last 4 bits, effectively performing num mod 16. The right shift operation num >> 4 discards the last 4 bits of num and shifts all higher bits 4 places to the right, effectively performing num // 16. These operations together perform integer division and modulus operations by 16, which are the key steps in decimal to hexadecimal conversion.

Identifying Problem Isomorphism

“Convert a Number to Hexadecimal” can be approximately mapped to “Binary to Text Converter”.

Both problems deal with the conversion between number systems or encoding formats. In “Convert a Number to Hexadecimal”, you are given a number, and have to convert this number into its hexadecimal representation.

In “Binary to Text Converter”, you’re given binary code, and you have to convert this binary code into its equivalent textual representation.

While these two problems deal with conversions, they do differ in terms of the specific conversion tasks, and the complexity involved. “Convert a Number to Hexadecimal” is simpler, involving conversion from base 10 to base 16, which is a fairly straightforward process that can be done using built-in language functions or straightforward mathematical operations.

“Binary to Text Converter” involves mapping binary representations to ASCII characters, which requires understanding of the ASCII table and might involve more complex string manipulation, making it a slightly more complex problem.

It’s crucial to understand the specific conversion rules and methods for each problem, and the general concept of converting between different formats or representations, in order to solve these types of problems.

10 Prerequisite LeetCode Problems

“Convert a Number to Hexadecimal” requires an understanding of number systems, bitwise operations, and string manipulation. Here are some simpler problems to prepare for it:

  1. 371. Sum of Two Integers: Understand bitwise operations.

  2. 191. Number of 1 Bits: Practice working with bits.

  3. 136. Single Number: More practice with bitwise XOR.

  4. 231. Power of Two: Understand binary representation.

  5. 67. Add Binary: Practice with binary to decimal conversion.

  6. 168. Excel Sheet Column Title: Practice with decimal to other bases conversion.

  7. 171. Excel Sheet Column Number: The reverse of problem 168.

  8. 190. Reverse Bits: Practice manipulating bits.

  9. 476. Number Complement: Learn how to find a complement of a number.

  10. 405. Convert a Number to Hexadecimal: This problem is similar to the problem at hand but slightly easier as you only have to convert to binary.

These cover bitwise operations and number system conversion, which are essential for solving the “Convert a Number to Hexadecimal” problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def toHex(self, num: int) -> str:
	if num == 0: return '0'
	map = '0123456789abcdef'
	result = ''

	if num < 0: num += 2 ** 32

	while num > 0:
		digit = num % 16
		num = (num-digit) // 16
		result += str(map[digit])

	return result[::-1]

Problem Classification

The problem statement can be classified into the following problem domains:

  1. Number Theory: The task involves understanding number systems and working with hexadecimal representations which fall under the umbrella of number theory.

  2. Bit Manipulation: The mention of two’s complement method suggests that bitwise operations might be necessary. Bit manipulation is typically used when dealing with binary representations of numbers, and converting between binary and other bases such as hexadecimal.

  3. String Manipulation: The task requires returning a string as the final output. Therefore, methods of constructing and manipulating strings would be relevant.

  4. Algorithmic: At a high level, this is an algorithmic problem because it involves converting a number from one form (decimal) to another (hexadecimal) following a specific set of rules.

Clarification Questions

What are the clarification questions we can ask about this problem?

Identifying Problem Isomorphism

Language Agnostic Coding Drills

  1. Understanding the hexadecimal system: Before diving into the code, the first thing to understand is the hexadecimal system. A hexadecimal is a 16-base number system. It uses the digits from 0 to 9 and the letters from A to F to represent the numbers from 10 to 15.

  2. Understanding two’s complement for negative numbers: Two’s complement is a mathematical operation on binary numbers. It’s the most common method of representing signed integers on computers. For this problem, if the input number is negative, we need to add 2^32 to it, which is equivalent to getting the two’s complement of a 32-bit integer.

  3. Looping until the number becomes zero: We need to repeatedly take the remainder of the number divided by 16 and use it to index into the ‘map’ string to get the hexadecimal digit. We then subtract the digit from the number and divide by 16 to get the next number to process. We keep doing this until the number becomes zero.

  4. Reversing the string: Finally, because we’ve built our hexadecimal number from least to most significant digit, we need to reverse it before returning it.

The problem solving approach:

  1. If the number is zero, we simply return ‘0’.
  2. If the number is negative, we add 2^32 to it to get its two’s complement.
  3. We create a ‘map’ string which maps digits to hexadecimal characters.
  4. We start a loop where we keep dividing the number by 16, and for each digit we get from this division, we prepend the corresponding character from the ‘map’ to our result.
  5. We stop when the number becomes zero.
  6. We reverse the result string and return it.

Targeted Drills in Python

Each of these drills might be smaller and simpler than the actual problem, but they represent the essential building blocks for constructing the final solution.

Drill 1: Understanding the hexadecimal system In this drill, you need to write a function that maps decimal numbers to hexadecimal characters. For example, the function should map 15 to ‘f’.

1
2
3
4
5

def decimal_to_hex(decimal):
    map = '0123456789abcdef'
    return map[decimal]

print(decimal_to_hex(15))  # Output: 'f'

Drill 2: Handling negative numbers using two’s complement In this drill, practice dealing with negative numbers by using two’s complement. Write a function that takes a negative integer and returns its two’s complement.

1
2
3
4

def twos_complement(negative_num):
    return negative_num + 2**32

print(twos_complement(-15))  # Output: 4294967281

Drill 3: Looping until the number becomes zero and building a string Here, you’ll implement the main logic of converting a number to hexadecimal. You should keep dividing the number by 16 and build the hexadecimal representation string from the remainder.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def build_hex(num):
    map = '0123456789abcdef'
    result = ''
    while num > 0:
        digit = num % 16
        num = (num - digit) // 16
        result += map[digit]
    return result[::-1]

print(build_hex(255))  # Output: 'ff'

Drill 4: Combining everything Finally, you can combine the above drills into the final solution. Handle the special cases where the number is zero or negative, and then use the function from Drill 3 to get the hexadecimal representation.

1
2
3
4
5
6
7
8

def to_hex(num):
    if num == 0: 
        return '0'
    if num < 0: 
        num = twos_complement(num)  # Use the function from Drill 2
    return build_hex(num)  # Use the function from Drill 3

print(to_hex(-1))  # Output: 'ffffffff'