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.

Data Scientist/MLE/SWE @takemobi