Skip to main content
Talentd

Sum of k-Mirror Numbers - Solution & Explanation

HardMathEnumeration21 min readAsked at: Microsoft, Meta, Cisco +2
Practice this problem

Problem Statement

A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k.

  • For example, 9 is a 2-mirror number. The representation of 9 in base-10 and base-2 are 9 and 1001 respectively, which read the same both forward and backward.
  • On the contrary, 4 is not a 2-mirror number. The representation of 4 in base-2 is 100, which does not read the same both forward and backward.

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

 

Example 1:

Input: k = 2, n = 5
Output: 25
Explanation:
The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25.

Example 2:

Input: k = 3, n = 7
Output: 499
Explanation:
The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

Example 3:

Input: k = 7, n = 17
Output: 20379000
Explanation: The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

 

Constraints:

  • 2 <= k <= 9
  • 1 <= n <= 30

Approach Overview

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.

Approach 1: Brute-force Generation

This approach involves a brute-force method where we generate all numbers starting from 1 and check if they are palindromic in both base-10 and base-k. We keep a count until we reach the desired number of k-mirror numbers.

This solution defines functions to check for palindromes and convert numbers to base-k. By iterating through numbers and checking both conditions, we ensure the numbers are k-mirror.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

Time Complexity: O(n*m), where n is the number of k-mirror numbers required, and m depends on the number being iterated over. Space Complexity: O(1) for space used in calculations.

Try this approach in the editor →

Approach 2: Palindrome Construction

This approach optimizes the search by constructing palindromic numbers directly. For each half-length, generate palindromes and convert to base-k to verify the k-mirror condition. This approach eliminates non-palindromes from checks.

In this Python solution, we pre-generate numeric palindromes instead of inspecting each number linearly, thereby enhancing efficiency. By iterating over possible palindromic lengths, we streamline the search space for k-mirror numbers.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

Time Complexity: Depending on the implementation details of palindrome generation and validation, it is much less than brute-force for larger n. Space Complexity: Depends on palindromic generation results.

Try this approach in the editor →

Approach 3: Half Enumeration + Mathematics

For a k-mirror number, we can divide it into two parts: the first half and the second half. For numbers with even length, the first and second halves are exactly the same; for numbers with odd length, the first and second halves are the same, but the middle digit can be any digit.

We can enumerate the numbers in the first half, and then construct the complete k-mirror number based on the first half. The specific steps are as follows:

  1. Enumerate Lengths: Start enumerating the length of the numbers from 1, until we find enough k-mirror numbers that meet the requirements.
  2. Calculate the Range of the First Half: For a number of length l, the range of the first half is [10^{(l-1)/2}, 10^{(l+1)/2}).
  3. Construct k-Mirror Numbers: For each number i in the first half, if the length is even, use i directly as the first half; if the length is odd, divide i by 10 to get the first half. Then reverse the digits of the first half and append them to form the complete k-mirror number.
  4. Check k-Mirror Numbers: Convert the constructed number to base k and check whether it is a palindrome.
  5. Accumulate the Result: If it is a k-mirror number, add it to the result and decrease the counter n. When n reaches 0, return the result.

The time complexity mainly depends on the length being enumerated and the range of the first half. Since the maximum value of n is 30, the number of enumerations is limited in practice. The space complexity is O(1), since only a constant amount of extra space is

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute-force Generation

Time Complexity: O(n*m), where n is the number of k-mirror numbers required, and m depends on the number being iterated over. Space Complexity: O(1) for space used in calculations.

Palindrome Construction

Time Complexity: Depending on the implementation details of palindrome generation and validation, it is much less than brute-force for larger n. Space Complexity: Depends on palindromic generation results.

Half Enumeration + Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute-force GenerationO(X log X)O(1)Useful for understanding the property of k‑mirror numbers or when constraints are extremely small.
Palindrome ConstructionO(n log_k V)O(1)Best approach. Generates only base‑10 palindromes and checks base‑k symmetry, drastically reducing candidate numbers.

Video Solution

Sum of k-Mirror Numbers | Super Detailed | Minute Details | Leetcode 2081 | codestorywithMIK • codestorywithMIK • 11,489 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of k-Mirror Numbers easy or hard?
LeetCode classifies Sum of k-Mirror Numbers as a Hard problem. The difficulty comes from recognizing that brute force is inefficient and that constructing palindromes directly dramatically reduces the search space.
Sum of k-Mirror Numbers Python/Java solution
Most implementations generate base‑10 palindromes, convert each candidate into base‑k, and check if that representation is also a palindrome. The same logic works across Python, Java, C++, JavaScript, and C# with only minor syntax differences for base conversion and string reversal.
How to solve Sum of k-Mirror Numbers in O(n)?
Pure O(n) time is not practical because each candidate must be converted to base‑k, which costs O(log_k V). The closest practical optimization is generating base‑10 palindromes directly and validating them in base‑k, giving about O(n log_k V) complexity.
What is the best approach for Sum of k-Mirror Numbers?
The most efficient approach constructs palindromes directly in base‑10 and then checks whether their base‑k representation is also a palindrome. This avoids scanning every integer and drastically reduces the number of candidates tested. The complexity is roughly O(n log_k V) where V is the size of generated palindromes.
Is Sum of k-Mirror Numbers asked at Google/Amazon/Meta?
This problem reflects patterns commonly used in big tech interviews such as number construction, base conversion, and palindrome checking. Similar enumeration and digit manipulation problems appear in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Sum of k-Mirror Numbers?
The solution mainly relies on numeric manipulation rather than complex data structures. String or array representations are often used during palindrome checks, and simple loops handle base conversion and enumeration.
What is the time complexity of Sum of k-Mirror Numbers?
The optimized palindrome construction approach runs in about O(n log_k V). Only base‑10 palindromes are generated, and each candidate requires a base‑k conversion plus a palindrome check. A naive brute-force solution can grow toward O(X log X) because it tests every integer until enough valid numbers are found.

Ready to solve this problem?

Practice Sum of k-Mirror Numbers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Prime Palindrome

Next

Strobogrammatic Number II