Sum of k-Mirror Numbers - Solution & Explanation

Problem Overview: A k-mirror number is a positive integer that is palindromic in both base‑10 and base‑k. Given integers k and n, compute the sum of the first n numbers that satisfy this property. Since n ≤ 30, the challenge is not large input size but efficiently generating candidates without scanning huge ranges of integers.

Approach 1: Brute-force Generation (Time: O(X log X), Space: O(1))

The direct strategy iterates through natural numbers starting from 1. For each number, check if it is a palindrome in base‑10 by comparing characters from both ends. Then convert the number to base‑k and check if the resulting representation is also a palindrome. If both conditions hold, add the number to the result and continue until n valid numbers are found.

This approach relies heavily on repeated base conversions and palindrome checks. Each conversion takes O(log_k V) time where V is the current number. Since many numbers are rejected before finding valid k‑mirror numbers, the search range grows quickly. The method is conceptually simple and useful for understanding the property of k‑mirror numbers, but it wastes time testing numbers that cannot possibly be valid.

Approach 2: Palindrome Construction (Time: O(n log_k V), Space: O(1))

A more efficient strategy generates only numbers that are already palindromes in base‑10. Instead of scanning every integer, construct palindromes digit by digit. For a given length, build the first half and mirror it to produce the full number. This enumeration guarantees every candidate is a base‑10 palindrome.

For each generated palindrome, convert it to base‑k and verify whether that representation is also a palindrome. If it passes the check, add it to the running sum. Continue generating palindromes in increasing order of length until n valid numbers are collected.

The key insight is reducing the search space. Palindromes are extremely sparse compared to all integers, so constructing them directly avoids millions of unnecessary checks. Base conversion still costs O(log_k V), but the number of candidates tested is much smaller.

Because the solution revolves around generating numeric patterns and verifying symmetry, the problem fits well under math and enumeration. The palindrome property itself is another key concept often reused in problems involving digit manipulation and number construction, closely related to techniques from palindrome problems.

Recommended for interviews: The palindrome construction approach is the one interviewers expect. Brute force demonstrates understanding of base conversion and palindrome checks, but constructing palindromes shows stronger algorithmic thinking because you shrink the candidate space dramatically. In practice, generating base‑10 palindromes and validating them in base‑k gives a clean and efficient solution that easily handles the constraint of finding the first 30 k‑mirror numbers.