Python itertools.product

2081. Sum of k-Mirror Numbers

This week’s (weekly 268)last question can be solved by checking all the possible numbers in a brute force way. In order to construct all the possible candidates, we can use backtracking based on standard approaches. If you are using python, luckily, we can use itertools.porduct directly to construct all the possibilities.

I put some comments in the code, so I will not provide extra explanations here.

digits = [str(i) for i in range(10)]
class Solution:
    def convert_baseK_to_base10(self, s, k):
        """
        convert a base k number to base 10 number
        """
        ret = 0
        for c in s:
            ret *= k
            ret += int(c)
        return ret

    
    def is_mirror_base10_number(self, s):
        """
        check whether this base 10 number in string is a mirror number
        """
        k = len(s) // 2
        return len(s) == 1 or s[:k] == s[-k:][::-1]
        
            
    def get_this_length_ret(self, length_, k):
        """
        Get the base k number with lenght of length_
        """
        if length_ == 1:return list(range(1, k))
		# construct all possible candidates for left mirror, then the right will be the reverse of the candidate.
        left = ("".join(candidate) for candidate in list(itertools.product(digits[:k], repeat = length_ // 2)))
       
        if length_ % 2 == 0:
            ret = [element + element[::-1] for element in left]
        else:
            ret = [element + str(i) + element[::-1] for element in left 
                                                    for i in range(k)]
        # check whether base k is valid
        ret = [self.convert_baseK_to_base10(element, k) for element in ret 
                                        if element[0] != "0"]
        # check whether base 10 is valid
        ret = [element for element in ret 
                       if self.is_mirror_base10_number(str(element))]
        return ret
            
    def kMirror(self, k: int, n: int) -> int:
        ret = []
		# construct number with a specified length. 
        for length_ in range(1, 1000000):
            ret += self.get_this_length_ret(length_, k)
            if len(ret) >= n:
                return sum(sorted(ret)[:n])

Thanks for reading.