Sum of k-Mirror Numbers
HardPrompt
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,
9is a 2-mirror number. The representation of9in base-10 and base-2 are9and1001respectively, which read the same both forward and backward. - On the contrary,
4is not a 2-mirror number. The representation of4in base-2 is100, 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 <= 91 <= n <= 30
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward method is to iterate through all positive integers, one by one. For each integer, we check if it satisfies the two conditions: being a palindrome in base-10 and being a palindrome in base-k. We continue this process until we have found n such numbers and then sum them up.
Algorithm
- Initialize
sum = 0,count = 0, andnum = 1. - Loop while
count < n:- Check if
numis a palindrome in base-10. - If it is, check if
numis a palindrome in base-k. - If both are true, add
numtosumand incrementcount. - Increment
num.
- Check if
- Return
sum.
Walkthrough
This approach involves a simple loop that starts from 1 and increments. In each iteration, the current number is tested. To test if a number is a k-mirror number, we need two helper functions: one to check for palindromes in base-10 and another for base-k. A number is converted to its string representation in the respective base, and then the string is checked for the palindrome property. We keep a count of the k-mirror numbers found and stop once we reach n.
class Solution { public long kMirror(int k, int n) { long sum = 0; int count = 0; long num = 1; while (count < n) { if (isBase10Palindrome(num) && isBaseKPalindrome(num, k)) { sum += num; count++; } num++; } return sum; } private boolean isBase10Palindrome(long num) { String s = Long.toString(num); int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; } private boolean isBaseKPalindrome(long num, int k) { String s = Long.toString(num, k); int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
Let `M` be the `n`-th k-mirror number. The algorithm iterates up to `M`. For each number `i` from 1 to `M`, it performs two palindrome checks. The checks take `O(log10(i))` and `O(log_k(i))` time, respectively. The total time complexity is approximately `O(M * log M)`.
Space
O(log M), where `M` is the `n`-th k-mirror number. This space is used to store the string representations of the numbers during the palindrome checks.
Trade-offs
Pros
Simple to understand and implement.
Correctness is easy to verify.
Cons
Highly inefficient and can be very slow. The
n-th k-mirror number can be very large, leading to a huge number of iterations.Checks many numbers that are not even base-10 palindromes, wasting a lot of computation.
A significant improvement over brute force is to only check numbers that are already palindromic in base-10. We can generate base-10 palindromes in increasing order and, for each, check if its base-k representation is also a palindrome. This avoids checking a vast majority of numbers that couldn't possibly be k-mirror numbers.
Algorithm
- Initialize
sum = 0andcount = 0. - Loop through potential palindrome lengths
len = 1, 2, 3, .... - For each
len, determine the length of the first half:halfLen = (len + 1) / 2. - Iterate through all possible first halves
i(as numbers from10^(halfLen-1)to10^halfLen - 1). - For each
i, get its string representations_half. - Construct the full base-10 palindrome string
pfroms_half. - Convert
pto a numbernum. - Check if
numis a palindrome in base-k. - If it is, add
numtosumand incrementcount. - Stop when
countreachesnand returnsum.
Walkthrough
Instead of checking every integer, we can generate only the numbers that are palindromes in base-10. Base-10 palindromes can be constructed from a "first half". For example, from the number 12, we can construct two palindromes: 1221 (even length) and 121 (odd length). We can generate these first halves (i = 1, 2, 3, ...) and from them construct the full palindromes. This ensures we generate them in increasing order. For each generated base-10 palindrome, we convert it to its base-k string representation and check if that is also a palindrome.
class Solution { public long kMirror(int k, int n) { long sum = 0; int count = 0; for (int len = 1; ; len++) { int halfLen = (len + 1) / 2; long start = (long) Math.pow(10, halfLen - 1); long end = (long) Math.pow(10, halfLen); for (long i = start; i < end; i++) { String firstHalf = Long.toString(i); StringBuilder secondHalf = new StringBuilder(firstHalf).reverse(); String palindromeStr; if (len % 2 == 1) { palindromeStr = firstHalf + secondHalf.substring(1); } else { palindromeStr = firstHalf + secondHalf.toString(); } long num = Long.parseLong(palindromeStr); if (isBaseKPalindrome(num, k)) { sum += num; count++; if (count == n) { return sum; } } } } } private boolean isBaseKPalindrome(long num, int k) { String s = Long.toString(num, k); int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
Let `M` be the `n`-th k-mirror number. The number of base-10 palindromes up to `M` is approximately `2 * sqrt(M)`. For each palindrome, we perform a base-k conversion and palindrome check, which takes `O(log_k(M))` time. The total time complexity is roughly `O(sqrt(M) * log_k(M))`.
Space
O(log M), where `M` is the `n`-th k-mirror number. This space is for storing string representations of the numbers.
Trade-offs
Pros
Much faster than the brute-force approach by drastically reducing the number of candidates.
Generates candidates in increasing order of value, which simplifies finding the
nsmallest ones.
Cons
Less efficient than generating base-k palindromes. For a small
k, base-10 palindromes are much more numerous than base-k palindromes of similar magnitude, so this approach still checks more candidates than necessary.
This approach leverages the small size of the base k (k <= 9). Instead of iterating through all numbers or all base-10 palindromes, we generate palindromic numbers in base k directly. Since k is small, these numbers are much sparser than base-10 palindromes. Each generated base-k palindrome is then converted to base-10 and checked if it's a palindrome. This significantly reduces the number of candidates to test, leading to a highly efficient solution.
Algorithm
- Initialize
sum = 0andcount = 0. - Loop through the length of the base-k representation,
len = 1, 2, 3, .... - For each
len, determine the length of the first half:halfLen = (len + 1) / 2. - Iterate through all possible first halves (as numbers from
k^(halfLen-1)tok^halfLen - 1). - For each first half
i, convert it to a base-k strings_half. - Construct the full base-k palindrome string
p_kfroms_half. - Convert
p_kto its base-10 valuenum. - Check if
numis a base-10 palindrome. - If yes, add
numtosumand incrementcount. - If
countreachesn, break all loops and returnsum.
Walkthrough
The core idea is to flip the problem: generate numbers that satisfy the base-k palindrome property and then test the base-10 property. We can generate base-k palindromes systematically by their length. For a given length len, we can construct all palindromes by generating their first half (of length (len+1)/2). The first half is a number whose base-k representation has halfLen digits. We can iterate through these first halves, construct the full base-k palindrome string, convert it to its base-10 value, and then check if this value is a base-10 palindrome.
class Solution { public long kMirror(int k, int n) { long sum = 0; int count = 0; for (int len = 1; ; len++) { int halfLen = (len + 1) / 2; long start = (long) Math.pow(k, halfLen - 1); long end = (long) Math.pow(k, halfLen); for (long i = start; i < end; i++) { String firstHalf = Long.toString(i, k); StringBuilder secondHalf = new StringBuilder(firstHalf).reverse(); String palindromeInBaseK; if (len % 2 == 1) { palindromeInBaseK = firstHalf + secondHalf.substring(1); } else { palindromeInBaseK = firstHalf + secondHalf.toString(); } long num = Long.parseLong(palindromeInBaseK, k); if (isBase10Palindrome(num)) { sum += num; count++; if (count == n) { return sum; } } } } } private boolean isBase10Palindrome(long num) { String s = Long.toString(num); int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; }}Complexity
Time
The complexity depends on the magnitude of the `n`-th k-mirror number, `M_n`. We generate base-k palindromes. The number of base-k palindromes of length up to `L = log_k(M_n)` is roughly `k * k^(L/2)`, which is proportional to `sqrt(M_n)`. For each candidate, conversion and checking takes `O(log M_n)` time. The performance is excellent for the given constraints because the number of candidates is very small.
Space
O(log_k M_n), where `M_n` is the `n`-th k-mirror number. This space is used to store the string representations of the numbers in base-10 and base-k.
Trade-offs
Pros
Highly efficient due to a much smaller search space (base-k palindromes), especially since
kis small.Directly generates candidates that satisfy one of the two palindrome conditions, minimizing wasted checks.
Cons
The logic for generating palindromes in a specific base can be slightly more complex to implement than simple iteration.
The generated numbers are not strictly in increasing order of their base-10 value (e.g., a number with a longer base-k representation can be smaller than one with a shorter representation), but grouping by length of the base-k representation keeps them manageable and finds them in a generally increasing order.
Solutions
Solution
class Solution {public long kMirror(int k, int n) { long ans = 0; for (int l = 1;; ++l) { int x = (int)Math.pow(10, (l - 1) / 2); int y = (int)Math.pow(10, (l + 1) / 2); for (int i = x; i < y; i++) { long v = i; for (int j = l % 2 == 0 ? i : i / 10; j > 0; j /= 10) { v = v * 10 + j % 10; } String ss = Long.toString(v, k); if (check(ss.toCharArray())) { ans += v; if (--n == 0) { return ans; } } } } }private boolean check(char[] c) { for (int i = 0, j = c.length - 1; i < j; i++, j--) { if (c[i] != c[j]) { return false; } } return true; }}class Solution {public: long long kMirror(int k, int n) { long long ans = 0; for (int l = 1;; ++l) { int x = pow(10, (l - 1) / 2); int y = pow(10, (l + 1) / 2); for (int i = x; i < y; ++i) { long long v = i; int j = (l % 2 == 0) ? i : i / 10; while (j > 0) { v = v * 10 + j % 10; j /= 10; } if (check(v, k)) { ans += v; if (--n == 0) { return ans; } } } } } private: bool check(long long x, int k) { vector<int> s; while (x > 0) { s.push_back(x % k); x /= k; } for (int i = 0, j = s.size() - 1; i < j; ++i, --j) { if (s[i] != s[j]) { return false; } } return true; }};class Solution: def kMirror(self, k: int, n: int) -> int: def check(x: int, k: int) -> bool: s = [] while x: s . append(x % k) x //= k return s == s[:: - 1] ans = 0 for l in count(1): x = 10 ** ((l - 1) // 2) y = 10 ** ((l + 1) // 2) for i in range(x, y): v = i j = i if l % 2 == 0 else i // 10 while j > 0: v = v * 10 + j % 10 j //= 10 if check(v, k): ans += v n -= 1 if n == 0: return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.