Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A k-mirror number must already be a decimal palindrome, so generate only those candidates instead of testing every positive integer. Mirroring a leading half constructs palindromes in increasing length and value, making the first n accepted candidates the smallest ones.

Approach

For each half-length, enumerate leading halves without leading zeros. First mirror them with the middle digit shared to create odd-length palindromes, then mirror them fully for even lengths. Convert each candidate to base k by repeated division and remainder extraction, and compare the digit list with its reversal. Its reversed collection order does not affect palindrome testing. Store successful candidates, stop at n, and return their sum.

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def base_k_is_pal(num):
            base_k = []
            while num:
                base_k.append(num % k)
                num //= k
            return base_k == base_k[::-1]

        res = []
        l = 1

        while len(res) < n:
            r = l * 10
            for p in [1, 0]:
                for i in range(l, r):
                    if len(res) == n:
                        break
                    copy = str(i)
                    if p == 0:
                        copy = copy + copy[::-1]
                    else:
                        copy = copy[:-1] + copy[::-1]
                    copy = int(copy)
                    if base_k_is_pal(copy):
                        res.append(copy)
            l = r

        return sum(res)

Complexity analysis

Let M be the nth accepted k-mirror number and P the number of decimal palindromes generated through M, with P = O(sqrt(M)). Under unit-cost arithmetic, time is O(P * log_k(M + 1)), including decimal mirroring, base-k conversion, palindrome checking and final summation. Since 2 <= k <= 9, decimal construction fits this bound. Auxiliary space is O(n + log_k(M + 1)) for accepted values and temporary digits/strings. The +1 includes M = 1.