800. Similar RGB Color

Approach 1: Check nearest neighbours two characters at a time

class Solution(object):
    def similarRGB(self, color):
        """
        :type color: str
        :rtype: str
        """
        ret = '#'
        def subtract(s1, s2):
            return abs(int(s1, 16)-int(s2, 16))
        di = {'0':['00','11'], '1':['00','11','22'], '2':['11','22','33'],'3':['22', '44', '33'], '4':['33', '44', '55'], '5':['44', '55', '66'], '6':['55','66','77'], '7':['66','77','88'], '8':['77','88', '99'], '9':['88','99','aa'], 'a':['99','aa','bb'], 'b':['aa','bb','cc'], 'c':['bb','cc','dd'], 'd':['cc','dd','ee'], 'e':['dd','ee','ff'],'f':['ee','ff']}
        for i in range(1,len(color),2):
            # print(color[i:i+2])
            mi = float('inf')
            part = ''
            for j in di[color[i]]:
                su = subtract(color[i:i+2],j)
                if su < mi:
                    part = j
                    mi = su
                # print(j, su, mi, part)
            ret += part
        return ret

For every pair of characters we will just check if their nearest shorthand characters have min sum, and keep on repeating this till we reach the end of the string

Time Complexity: O(1)

Space Complexity: O(1)

Approach 2: Use more advanced math

Since we're evaluating the decimal form of the hex pairs, it might be easier for us to find out which one of the nearest neighbours it is. It'll be either before or after the first pairwise character.

Using some quick math this math becomes evident

class Solution(object):
    def similarRGB(self, color):
        """
        :type color: str
        :rtype: str
        """
        def close(s):
            a,b = divmod(int(s, 16), 17)
            if b > 8: a += 1
            a = hex(a)[-1]
            return a + a
        return '#' + close(color[1:3]) + close(color[3:5]) + close(color[5:])

Time Complexity: O(1)

Space Complexity: O(1)

This solution is faster even thought the time complexity is the same because for each pair we were iterating through three neighbours to find the right value, but here it just takes one division to figure out the closest neighbour