Problem description

Algorithm walkthrough

• Use helper function 1 to change a number into base k
• Use helper function 2 to check if a number is a palindrome
• In the main function, find n numbers that are both palindromes in base 10 and base k

Naive approach, check every number

Time complexity: O(M × log(M))

Let M = the value of the nth k-mirror number

1. Main Loop: We iterate through numbers 1, 2, 3, ..., M
   • Iterations: O(M)
2. For each number i:
   • Base-10 palindrome check: O(log₁₀(i))
   • Base conversion: O(log_k(i))
   • Base-k palindrome check: O(log_k(i))
   • Total per iteration: O(log₁₀(i) + log_k(i)) = O(log(i))
3. Overall Complexity: ∑(i=1 to M) O(log(i)) = O(M × log(M))

   class Solution:
    def kMirror(self, k: int, n: int) -> int:
        # helper function 1: change a number into base k
        # helper function 2: check if a number is a palindrome
        # main function, find n numbers that is both palindromes in base 10 and base k
        def change_base(number: int, base: int) -> str:
            res = ''
            remainder = number % base
            carry = number // base
            while (carry>0):
                res = str(remainder) + res
                remainder = carry % base
                carry = carry // base
            # Add the final remainder
            res = str(remainder) + res
            return res
        def is_parlindrome(number: str) -> bool:
            return number == number[::-1]
        res_list = []
        cur_num = 1
        while (len(res_list)<n):
            num2 = change_base(cur_num, k)
            if (is_parlindrome(str(cur_num)) and is_parlindrome(num2)):
                res_list.append(cur_num)
            cur_num += 1
        return sum(res_list)
   

A better way, only check the palidromes in base 10

Time complexity: O(P × log(M))

Let P = number of base-10 palindromes we need to check to find n k-mirror numbers

1. Palindrome Generation:
2. We only check base-10 palindromes

3. Iterations: O(P)

4. For each palindrome p:

5. Base conversion: O(log_k(p))
6. Base-k palindrome check: O(log_k(p))

7. Total per iteration: O(log_k(p)) = O(log(p))

8. Overall Complexity: ∑(p in first P palindromes) O(log(p)) = O(P × log(M))

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        # helper function 1: change a number into base k
        # helper function 2: check if a number is palindromes
        # main function, find n numbers that is both parlindromes in base 10 and base k
        def change_base(number: int, base: int) -> str:
            res = ''
            remainder = number % base
            carry = number // base
            while (carry>0):
                res = str(remainder) + res
                remainder = carry % base
                carry = carry // base
            # Add the final remainder
            res = str(remainder) + res
            return res
        def is_palindrome(number: str) -> bool:
            return number == number[::-1]
        def generate_base10_palindromes():
            """
            Generate palindromes in base-10 in ascending order.
            This is the key optimization - only check base-10 palindromes!
            """
            # Single digits (1-9)
            for i in range(1, 10):
                yield i

            # Multi-digit palindromes by length
            length = 2
            while True:
                # Even-length palindromes (11, 22, ..., 1001, 1111, ...)
                if length % 2 == 0:
                    half_len = length // 2
                    start = 10 ** (half_len - 1)
                    end = 10 ** half_len

                    for i in range(start, end):
                        s = str(i)
                        palindrome = int(s + s[::-1])
                        yield palindrome

                # Odd-length palindromes (101, 111, 121, ..., 10101, 10201, ...)
                else:
                    half_len = length // 2
                    start = 10 ** (half_len - 1) if half_len > 0 else 1
                    end = 10 ** half_len

                    for i in range(start, end):
                        s = str(i)
                        for middle in '0123456789':
                            palindrome = int(s + middle + s[::-1])
                            yield palindrome

                length += 1
        # Main algorithm: only check base-10 palindromes for base-k palindrome property
        total = 0
        count = 0

        for palindrome in generate_base10_palindromes():
            base_k_repr = change_base(palindrome, k)
            if is_palindrome(base_k_repr):
                total += palindrome
                count += 1
                if count == n:
                    break

        return total