[Leetcode] 2081. Sum of k-Mirror Numbers

https://leetcode.com/problems/sum-of-k-mirror-numbers/?envType=daily-question&envId=2025-06-23

initial

brute force way causes tle for some cases but the general approach is the same

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def converToKBaseString(hola,k):
            digits = []
            while hola:
                remainder=hola%k
                digits.append(str(remainder))
                hola//=k
            return ''.join(digits[::-1])

        count=0
        ans=0
        i=1
        while True:
            if count==n:
                break
            string_i = str(i)
            if string_i==string_i[::-1]:
                string_base_i = converToKBaseString(i,k)
                if string_base_i==string_base_i[::-1]:
                    ans+=i
                    count+=1
            i+=1
        return ans
        

sol

so using yield as generator to generate palindromes https://velog.io/@whitehousechef/Python-yield

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def converToKBaseString(hola,k):
            digits = []
            while hola:
                remainder=hola%k
                digits.append(str(remainder))
                hola//=k
            return ''.join(digits[::-1])

        def generatePalindrome():
            for i in range(1,10):
                yield i

            digits=1

            while True:
                digits+=1
                half = (digits+1)//2
                start = 10**(half-1)
                end = 10**half
                for i in range(start,end):
                    s=str(i)

                    if digits%2==0:
                        right_part=s[::-1]
                        palin = s+right_part
                    else:
                        right_part=s[-2::-1]
                        palin = s+right_part
                    yield int(palin)

        count=0
        ans=0
        i=1
        for palin in generatePalindrome():
            if count==n:
                break
            
            palin_k_base = converToKBaseString(palin,k)
            if palin_k_base==palin_k_base[::-1]:
                ans+=palin
                count+=1
        return ans
        

complexity

Overall: O(P × log_k(M)) time
so we generate p number of palindromes
converting int M to base k takes log_k(M) time
checking if that base k string is a palindrome takes log_k(M) cuz the number of digits in that string is log_k(M)

see the time and space for converting to base-k
https://velog.io/@whitehousechef/Converting-to-base-k-from-base-10-and-vice-versa

space is O(log_k(M)) cuz we are storing that many digits in the list and string