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 of9
in base-10 and base-2 are9
and1001
respectively, which read the same both forward and backward. - On the contrary,
4
is not a 2-mirror number. The representation of4
in 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 <= 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;
}
}
}
}
};