##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2081.html

# 2081. Sum of k-Mirror Numbers (Hard)

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

Companies:
Cisco

Related Topics:
Math, Enumeration

Similar Questions:

## Solution 1. Generating Palindromes

Enumerate palindrom numbers in base-10 and check if the corresponding base-k number is also a palindrome.

// OJ: https://leetcode.com/problems/sum-of-k-mirror-numbers/
class Solution {
long long getPalindrome(int half, bool odd) {
long long n = half, tmp = half;
if (odd) tmp /= 10;
while (tmp) {
n = n * 10 + tmp % 10;
tmp /= 10;
}
return n;
}
bool isPalindromeBaseK(long long n, int k) {
string s;
while (n) {
s += '0' + n % k;
n /= k;
}
int i = 0, j = s.size() - 1;
while (i < j && s[i] == s[j]) ++i, --j;
return i >= j;
}
public:
long long kMirror(int k, int n) {
long long ans = 0;
for (int len = 1; true; ++len) {
for (int half = pow(10, len - 1); half < pow(10, len); ++half) {
auto pal = getPalindrome(half, true);
if (isPalindromeBaseK(pal, k)) {
ans += pal;
if (--n == 0) return ans;
}
}
for (int half = pow(10, len - 1); half < pow(10, len); ++half) {
auto pal = getPalindrome(half, false);
if (isPalindromeBaseK(pal, k)) {
ans += pal;
if (--n == 0) return ans;
}
}
}
}
};


Another implementation:

// OJ: https://leetcode.com/problems/sum-of-k-mirror-numbers/
class Solution {
long getPalindrome(int half, bool odd) {
long pal = half;
if (odd) half /= 10;
for (; half; half /= 10) pal = pal * 10 + half % 10;
return pal;
}
bool isPalindromeBaseK(long n, int k) {
long mul = 1;
while (mul * k <= n) mul *= k;
for (; n; mul /= k * k) {
if (n / mul != n % k) return false;
n = (n - (n / mul) * mul - n % k) / k;
}
return true;
}
public:
long long kMirror(int k, int n) {
long long ans = 0;
for (int len = 1; true; ++len) {
int begin = pow(10, (len - 1) / 2), end = pow(10, (len + 1) / 2);
for (int half = begin; half < end; ++half) {
long pal = getPalindrome(half, len % 2);
if (isPalindromeBaseK(pal, k)) {
ans += pal;
if (--n == 0) return ans;
}
}
}
}
};


Or we can do it in the reverse order – enumerate palindrome numbers in base-k, then check if the corresponding base-10 number is a palindrome.

// OJ: https://leetcode.com/problems/sum-of-k-mirror-numbers/
class Solution {
long long getPalindromeBaseK(int half, int k, bool odd) {
long long ans = half;
if (odd) half /= k;
while (half) {
ans = ans * k + half % k;
half /= k;
}
return ans;
}
bool isPalindromeBase10(long long n) {
string s;
while (n) {
s += '0' + n % 10;
n /= 10;
}
int i = 0, j = s.size() - 1;
while (i < j && s[i] == s[j]) ++i, --j;
return i >= j;
}
public:
long long kMirror(int k, int n) {
long long ans = 0;
for (int len = 1; true; ++len) {
for (int half = pow(k, len - 1); half < pow(k, len); ++half) {
auto pal = getPalindromeBaseK(half, k, true);
if (isPalindromeBase10(pal)) {
ans += pal;
if (--n == 0) return ans;
}
}
for (int half = pow(k, len - 1); half < pow(k, len); ++half) {
auto pal = getPalindromeBaseK(half, k, false);
if (isPalindromeBase10(pal)) {
ans += pal;
if (--n == 0) return ans;
}
}
}
}
};