405.Convert a Number to Hexadecimal

Tags: [num], [bit], [hex]

Link: https://leetcode.com/problems/convert-a-number-to-hexadecimal/?tab=Description

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1. All letters in hexadecimal (a-f) must be in lowercase.
2. The hexadecimal string must not contain extra leading0s. If the number is zero, it is represented by a single zero character'0'; otherwise, the first character in the hexadecimal string will not be the zero character.
3. The given number is guaranteed to fit within the range of a 32-bit signed integer.
4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Example 2:

Input:
-1

Output:
"ffffffff"

Solution: num, bit, hex

class Solution(object):
    def toHex(self, num):
        """
        :type num: int
        :rtype: str
        """
        if not num:
            return '0'

        digits = [str(x) for x in xrange(10)]
        digits += ['a', 'b', 'c', 'd', 'e', 'f']
        digits_map = {}
        for i in xrange(len(digits)):
            digits_map[digits[i]] = i

        result = []
        is_negative_num = False
        if num < 0:
            num = -num
            is_negative_num = True

        while num > 0:
            result.append(digits[num % 16])
            num /= 16

        if is_negative_num:
            result += ['0' for _ in xrange(8 - len(result))]

            # invert digits
            for i in xrange(len(result)):
                result[i] = digits[15 - digits_map[result[i]]]

            # plus 1
            carry = 1
            for i in xrange(len(result)):
                tmp_sum = digits_map[result[i]] + carry
                if tmp_sum < 16:
                    result[i] = digits[tmp_sum]
                    carry = 0
                else:
                    result[i] = digits[tmp_sum % 16]
                    carry = tmp_sum / 16

        return ''.join(reversed(result))

Revelation:

• 32 bits binary representation is equal to 8 digits hex presentation. 4 bits is 1 hex digit.

Note:

• Two's complement is a way to represent the number, which is commonly used in computers.
• For example, if we want to represent -X, we can use binary-representation or hex-representation or ... to represent X, then in the binary format or hex format or ..., invert each digits, finally plus 1 on the binary-representation or hex representation or other representation.
• ???Time complexity = O(num), not sure the time complexity.