2081. Sum of k-Mirror Numbers

This problem shows up in interview settings because it’s a compact way to test multiple “core” skills at once. You need to be comfortable switching between number systems (base-10 vs. base-k), recognize when a brute-force scan will blow up, and design a cleaner search by enumerating only meaningful candidates (base-10 palindromes) in increasing order. On top of that, it checks your ability to implement palindrome validation efficiently, handle small but strict constraints correctly.

Problem statement

A k-mirror number is a positive integer with no leading zeros that is a palindrome in base-10 and in base-k.

For example, if k = 2, then:

• 3 is a 2-mirror number because it reads the same forwards and backwards in both bases:
  • Base-10 representation: 3
  • Base-2 representation: 11
• 4 is not a 2-mirror number because the base-2 representation is not symmetric:
  • Base-10 representation: 4
  • Base-2 representation: 100

Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

Constraints:

• 2 ≤ k ≤ 9
• 1 ≤ n ≤ 30

Examples

A naive approach

A natural first attempt is to iterate over positive integers (x=1,2,3,…) and do two checks for each number:

• Check if x is a palindrome in base 10.
• Convert x to base k and check if it is a palindrome there as well.

This approach is correct, but it takes a lot of work. Most numbers are not palindromes in base 10, so the algorithm spends most of its time rejecting values that will never qualify.

So, let’s think of a better solution.

Intuition for an optimal solution

The key optimization is: instead of checking every integer, we should generate only those numbers that are already palindromes in base 10.

As given in the problem statement, a k-mirror number must satisfy two conditions:

1. It reads the same forward and backward in base 10.
2. It also reads the same forward and backward in base k.

If we scan integers normally, the first condition eliminates most values, because base-10 palindromes are relatively rare. That means checking every integer spends a large amount of time on numbers that fail immediately.

A better strategy is to start by building base-10 palindromes directly. This way, every number we produce already meets the base-10 requirement, and the only remaining work is to convert it to base-k and check whether that representation is also a palindrome.

Optimized solution: Palindrome generation + base-k check

The algorithm generates decimal palindromes in increasing order using a simple half and mirror method.

For a chosen prefix (half\text{half}half), there are two ways to form a palindrome:

• Odd length: Mirror half\text{half}half but skip its last digit, so the middle digit is not repeated.
• Even length: Mirror the entire half\text{half}half.

This guarantees that every produced number is a palindrome in base 10. After that, we convert the same number to base k and check whether its base-k digits also form a palindrome. Each time the check succeeds, we add the number to the running sum and increase the count. We stop as soon as we have found n such numbers.

Because these decimal palindromes are generated in increasing order, the first n numbers that pass the base-k check are exactly the n smallest k-mirror numbers.

Step-by-step algorithm

1. Initialize counters and the half range. Set start = 1 indicating that the first set of prefixes (half) will be 1 to 9. Set k_mirrored = 0 to count how many k-mirror numbers have been found. Set total = 0 to store the sum of the found k-mirror numbers.
2. While k_mirrored < n, keep generating base-10 palindromes and checking them.
   1. Compute end = start * 10. This makes the current prefix range: half in [start, end).
      1. If start = 1, then half is 1..9.
      2. If start = 10, then half is 10..99.
      3. If start = 100, then half is 100..999, and so on.
3. For each half in the current range, form palindromes in two ways: Odd-length palindrome (mode = 0) and even-length palindrome (mode = 1).
   1. Build the decimal palindrome from half. Start with pal = half.
   2. Set the part to mirror:
      1. If mode == 0 (odd), set tail = half // 10.
      2. If mode == 1 (even), set tail = half.
   3. While tail is not zero:
      1. Append the last digit of tail to pal using: pal = pal * 10 + (tail % 10).
      2. Remove the last digit of tail using: tail //= 10.
   4. Check whether the same number is also a palindrome in base k. Call the helper function isPalK(k, pal). If it returns TRUE, then:
      1. Increase the count as k_mirrored += 1.
      2. Add to the sum as total += pal.
   5. If k_mirrored reaches n, stop searching.
4. After finishing both modes for the current range, update start = end. This moves from 1-digit prefixes to 2-digit prefixes, then 3-digit prefixes, and so on.
5. Once k_mirrored == n, return total.

How isPalK(k, num) works?

• Convert num into base k by repeatedly taking remainders:
  • Each step appends num % k to a list of digits. Then update num //= k to continue.
• After conversion, check if the digit list is the same forwards and backwards:
  • Return digs == digs[::-1].

Solution code implementation in Python

Let’s look at the code of the optimal solution approach we just discussed.

def kMirror(k, n):
    start = 1   # start of the current "half" range (1, then 10, then 100, ...)
    k_mirrored = 0     # how many k-mirror numbers found so far
    total = 0   # running sum of found k-mirror numbers

    # Keep generating candidates until we find n valid k-mirror numbers
    while k_mirrored < n:
        end = start * 10  # end (exclusive) of the current "half" range

        # mode=0 => odd-length decimal palindromes (mirror half without last digit)
        # mode=1 => even-length decimal palindromes (mirror full half)
        for mode in (0, 1):
            # half is the "prefix" we mirror to form a full decimal palindrome
            for half in range(start, end):
                if k_mirrored == n:
                    break

                pal = half  # start palindrome as the prefix itself

                # For odd-length palindromes, skip the last digit when mirroring
                # (prevents duplicating the middle digit)
                tail = half // 10 if mode == 0 else half

                # Append the reverse of tail to pal to form the full palindrome in base-10
                # Example odd:  half=123, tail=12  => pal: 123 -> 1232 -> 12321
                # Example even: half=123, tail=123 => pal: 123 -> 1233 -> 12332 -> 123321
                while tail:
                    pal = pal * 10 + (tail % 10)
                    tail //= 10

                # pal is palindrome in base-10 by construction; check base-k palindrome
                if isPalK(k, pal):
                    k_mirrored += 1
                    total += pal

        # Move to the next digit-length for half (1..9 -> 10..99 -> 100..999 -> ...)
        start = end

    return total
    
    
def isPalK(k, num):
    # Convert num to base-k digits (least-significant first)
    digs = []
    while num:
        digs.append(num % k)
        num //= k
    # Palindrome if digits read the same forward and backward
    return digs == digs[::-1]


# Driver code
def main():
    test_cases = [
        (3, 6),    
        (4, 5),    
        (5, 7),    
        (9, 10),   
        (2, 15),  
    ]

    for i, (k, n) in enumerate(test_cases, 1):
        ans = kMirror(k, n)
        print(f"{i}.\tk = {k}, n = {n}")
        print(f"\n\tOutput: {ans}")
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity

The algorithm generates decimal palindromes and checks each one in base-k. If T palindromes are tested before finding n valid numbers, and X is the largest tested value, then the complexity becomes:

$O(T×(log⁡⁡_{10}(X)+log⁡⁡k(X))$

This reduces to constant time, O(1), under the problem constraints because n ≤ 30 and 2 ≤ k ≤ 9. These fixed limits place an upper bound on how many palindromes are tested and how large X can become, so the total work is bounded by a constant for all valid inputs.

Space complexity

The algorithm stores the base-k digits of one palindrome at a time, which requires $O(\log_{k} (X)$ space.

Can we simplify further?

Yes. Because the constraints are small and fixed, 2 ≤ k ≤ 9 and n ≤ 30, it is possible to precompute the first 30 k-mirror numbers for every base k in [2, 9]. Once those lists are precomputed, the runtime solution becomes a direct lookup followed by summation. This removes the need to generate palindromes, convert bases, or perform palindrome checks during execution.

The solution below uses a precomputed table. For each base k from 2 to 9, ANS[k-2] already stores the first 30 k-mirror numbers. For an input (k, n), it simply takes the first n numbers from that list and returns their sum, so no palindrome generation or base conversion is done at runtime.

class Solution:
    # Precomputed k-mirror numbers for k = 2..9 (each list contains the first 30)
    ANS = [
        [
            1, 3, 5, 7, 9, 33, 99, 313, 585, 717,
            7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585,
            1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485,
            13500531, 719848917, 910373019, 939474939,
        ],
        [
            1, 2, 4, 8, 121, 151, 212, 242, 484, 656,
            757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848,
            1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375,
            7875787, 7949497, 27711772, 83155138,
        ],
        [
            1, 2, 3, 5, 55, 373, 393, 666, 787, 939,
            7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122,
            3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165,
            5679765, 53822835, 623010326, 954656459, 51717171715,
        ],
        [
            1, 2, 3, 4, 6, 88, 252, 282, 626, 676,
            1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303,
            47633674, 65977956, 808656808, 831333138, 831868138, 836131638,
            836181638, 2512882152, 2596886952, 2893553982, 6761551676,
            12114741121, 12185058121,
        ],
        [
            1, 2, 3, 4, 5, 7, 55, 111, 141, 191,
            343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647,
            168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624,
            4298924, 4516154, 4565654,
        ],
        [
            1, 2, 3, 4, 5, 6, 8, 121, 171, 242,
            292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749,
            61255216, 230474032, 466828664, 485494584, 638828836, 657494756,
            858474858, 25699499652, 40130703104, 45862226854, 61454945416,
            64454545446,
        ],
        [
            1, 2, 3, 4, 5, 6, 7, 9, 121, 292,
            333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662,
            30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791,
            4198914, 55366355,
        ],
        [
            1, 2, 3, 4, 5, 6, 7, 8, 191, 282,
            373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605,
            626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881,
            2401042, 2434342, 2442442,
        ],
    ]

    def kMirror(self, k, n):
        # k is in [2..9], so k-2 maps it into ANS index [0..7]
        return sum(Solution.ANS[k - 2][:n])


# Driver code (custom tests, not the LeetCode statement examples)
def main():
    solver = Solution()

    test_cases = [
        (3, 6),
        (4, 5),
        (5, 10),
        (7, 12),
        (9, 15),
    ]

    for i, (k, n) in enumerate(test_cases, 1):
        ans = solver.kMirror(k, n)
        print(f"{i}.\tk = {k}, n = {n}")
        print(f"\tOutput: {ans}")
        print("-" * 60)


if __name__ == "__main__":
    main()

Common mistakes to avoid and interview tips

Even though the idea sounds simple (generate palindromes and check base-k), most bugs happen in the small details below.

• Generating palindromes incorrectly:
  • Odd vs even length mirroring confusion: For odd-length palindromes, you must skip the last digit of the half before mirroring. Otherwise, you duplicate the middle digit and create the wrong number.
  • Starting halves from the wrong range: If your half length is L, the half should typically range from 10^(L-1) to 10^L - 1 to avoid leading zeros in the final palindrome.
• Base conversion pitfalls:
  • Forgetting the “x = 0” case: Here, we only generate positive candidates, so it won’t happen, but if you reuse conversion code elsewhere, 0 should become [0] not an empty list.
  • Checking palindrome on a string with leading zeros: Don’t pad base-k representations with zeros. Palindromes must be checked on the natural representation (no leading zeros).
• Emphasize why you generate base-10 palindromes instead of scanning all integers: It prunes the search dramatically because base-10 palindrome density is low compared to all integers.