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.
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; }}Video 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.