LeetCode 2081 - Sum of k-Mirror Numbers
The problem asks us to find the sum of the n smallest k-mirror numbers, where a k-mirror number is a positive integer that reads the same forwards and backwards both in base-10 and in base-k.
Difficulty: 🔴 Hard
Topics: Math, Enumeration
Solution
Problem Understanding
The problem asks us to find the sum of the n smallest k-mirror numbers, where a k-mirror number is a positive integer that reads the same forwards and backwards both in base-10 and in base-k. The inputs are k, representing the base for the mirror property, and n, the count of the smallest numbers we must sum. The expected output is a single integer representing the sum of these numbers.
For example, if k = 2 and n = 5, we need the 5 smallest numbers that are palindromes in both base-10 and binary. The constraints 2 <= k <= 9 and 1 <= n <= 30 indicate that n is small, which is significant because the smallest numbers we need are not extremely large and we can generate them in order of magnitude.
Key points are that numbers cannot have leading zeros, which affects the generation of palindromes, and the number must satisfy two palindromic conditions simultaneously. Edge cases include very small bases like k=2, which quickly makes higher numbers in base-k long and non-palindromic, and numbers like n=1, which tests the minimal case.
Approaches
The brute-force approach is straightforward: iterate over all positive integers, convert each to base-k, check if both its decimal and base-k representations are palindromes, and sum the first n numbers found. While this works for very small numbers, it is inefficient because the first 30 k-mirror numbers for bases like 2 or 3 may require checking thousands of integers.
The optimal approach relies on the insight that we can generate base-10 palindromes directly, rather than checking each integer. Once we generate a decimal palindrome, we convert it to base-k and check if it is a palindrome there. This approach is efficient because palindromes are sparse compared to all integers, and we only generate numbers that are likely candidates. We can generate palindromes systematically by creating numbers digit by digit, both odd-length and even-length, ensuring no leading zeros.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(L * log n) | O(n) | Check every number for decimal and base-k palindromic property; inefficient for larger numbers |
| Optimal | O(n * log^2 N) | O(n) | Generate decimal palindromes only, check base-k palindromicity; scales well for small n |
Algorithm Walkthrough
- Initialize an empty list
resultsto store the k-mirror numbers. - Start generating decimal palindromes starting from length 1.
- For each palindrome length, generate all palindromes without leading zeros. There are two types: even-length and odd-length palindromes.
- For each generated decimal palindrome:
a. Convert it to base-k.
b. Check if the base-k representation is a palindrome.
c. If it is, append it to results.
5. Continue generating palindromes and checking until len(results) == n.
6. Return the sum of the numbers in results.
Why it works: By generating decimal palindromes systematically from smallest to largest, and checking the base-k palindrome condition, we ensure we find the n smallest numbers without missing any candidate. The invariant is that all numbers in results are valid k-mirror numbers and in ascending order.
Python Solution
class Solution:
def kMirror(self, k: int, n: int) -> int:
def is_palindrome(s: str) -> bool:
return s == s[::-1]
def to_base(num: int, base: int) -> str:
if num == 0:
return "0"
digits = []
while num > 0:
digits.append(str(num % base))
num //= base
return "".join(digits[::-1])
results = []
length = 1
while len(results) < n:
half = (length + 1) // 2
start = 10 ** (half - 1)
end = 10 ** half
for i in range(start, end):
s = str(i)
if length % 2 == 0:
pal = int(s + s[::-1])
else:
pal = int(s + s[-2::-1])
if is_palindrome(to_base(pal, k)):
results.append(pal)
if len(results) == n:
break
length += 1
return sum(results)
The Python solution defines helper functions is_palindrome to check strings and to_base to convert integers to a base-k string. We generate palindromes by constructing the first half of the number and mirroring it. For odd lengths, we skip duplicating the middle digit. We check each palindrome's base-k representation and add it to the results once it is valid.
Go Solution
import "strconv"
func kMirror(k int, n int) int64 {
isPalindrome := func(s string) bool {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
toBase := func(num int, base int) string {
if num == 0 {
return "0"
}
digits := []byte{}
for num > 0 {
digits = append(digits, byte(num%base)+'0')
num /= base
}
for i, j := 0, len(digits)-1; i < j; i, j = i+1, j-1 {
digits[i], digits[j] = digits[j], digits[i]
}
return string(digits)
}
var results []int
length := 1
for len(results) < n {
half := (length + 1) / 2
start := 1
for i := 1; i < half; i++ {
start *= 10
}
end := start * 10
for i := start; i < end; i++ {
s := strconv.Itoa(i)
var pal int
if length%2 == 0 {
rev := []byte(s)
for l, r := 0, len(rev)-1; l < r; l, r = l+1, r-1 {
rev[l], rev[r] = rev[r], rev[l]
}
pal, _ = strconv.Atoi(s + string(rev))
} else {
rev := []byte(s[:len(s)-1])
for l, r := 0, len(rev)-1; l < r; l, r = l+1, r-1 {
rev[l], rev[r] = rev[r], rev[l]
}
pal, _ = strconv.Atoi(s + string(rev))
}
if isPalindrome(toBase(pal, k)) {
results = append(results, pal)
if len(results) == n {
break
}
}
}
length++
}
var sum int64
for _, val := range results {
sum += int64(val)
}
return sum
}
The Go solution mirrors the Python logic but uses byte slices for string manipulation and conversion. Special attention is given to building palindromes and reversing slices efficiently. The sum uses int64 to prevent overflow for larger numbers.
Worked Examples
Example 1: k = 2, n = 5
Generate decimal palindromes: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, ...
Check base-2 representation for palindromicity:
1 -> 1 (yes), 2 -> 10 (no), 3 -> 11 (yes), 5 -> 101 (yes), 7 -> 111 (yes), 9 -> 1001 (yes)
Resulting 5 numbers: 1, 3, 5, 7, 9
Sum = 25
Example 2: k = 3, n = 7
Decimal palindromes: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, ...
Check base-3 palindromes:
1 -> 1 (yes), 2 -> 2 (yes), 4 -> 11 (yes), 8 -> 22 (yes), 121 -> 11111 (yes), 151 -> 12121 (yes), 212 -> 21212 (yes)
Sum = 499
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n * log^2 N) | Generating decimal palindromes up to n valid numbers; converting each to base-k takes O(log N) |
| Space | O(n) | Store the n k-mirror numbers in a list for summation |
The time complexity is dominated by the number of palindromes we generate and the base conversion. Since n is small (<=30), this approach is efficient in practice.