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

All Problems

All Solutions