2081-k 镜像数字的和

一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。

• 比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
• 相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。

给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。

示例 1：

**输入：** k = 2, n = 5
**输出：** 25
**解释：** 最小的 5 个 2 镜像数字和它们的二进制表示如下：
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。

示例 2：

**输入：** k = 3, n = 7
**输出：** 499
**解释：** 7 个最小的 3 镜像数字和它们的三进制表示如下：
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。

示例 3：

**输入：** k = 7, n = 17
**输出：** 20379000
**解释：** 17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

提示：

• 2 <= k <= 9
• 1 <= n <= 30

方法一：折半搜索

思路与算法

最容易想到的办法是从 1 开始递增地依次搜索每一个数。当我们搜索到数 i 时，如果 i 是回文的，并且 i 的 k 进制表示也是回文的，那么我们就将 i 加入答案。当我们搜索到 n 个符合要求的数后，就可以停止搜索并返回答案。

但这样搜索会超出时间限制。当 k = 7 时，第 30 个满足要求的数为 64454545446 \approx 6 \times 10^{10。即使对于每个数我们可以 O(1) 判断其是否符合要求，搜索到 64454545446 需要的时间也是远远大于时间限制的。

因此我们可以考虑进行「折半」搜索。因为 i 本身是回文的，我们可以搜索 i 的一半 i’，然后将 i’ 翻转并且拼接在 i’ 的后面，这样就得到了 i。这样「折半」搜索的好处在于：我们得到的 i 一定是回文的，这样大大减少了搜索空间，例如在所有小于等于 10^{10 的数中，原来的搜索方法需要搜索全部的 10^{10 个数，而使用「折半」搜索只需要搜索 O(\sqrt{10^{10} }) = O(10^5) 个回文数。

在将 i’ 拼接成 i 时，需要注意有两种拼接方法，即回文数的长度有奇有偶。例如当 i’ = 123 时，可以拼接得到 12321 或者 123321，具体取决于是将 i’ 的个位数作为奇数长度回文数的回文中心，还是直接将 i’ 翻转并拼接，得到一个长度为偶数的回文数。

为了递增地搜索 i，我们同样需要递增地搜索 i’。对于同一个 i’，偶数长度的回文数的值一定大于奇数长度的回文数的值，因此我们需要按照如下的方法进行搜索：

• 我们规定搜索的范围，i’ 需要在 [10^k, 10^{k+1}) 的范围内；

• 我们在该范围内递增枚举 i’，通过 i’ 构造出奇数长度的回文数，并判断其是否符合要求；

• 我们在该范围内递增枚举 i’，通过 i’ 构造出偶数长度的回文数，并判断其是否符合要求。

这样一来，我们就可以保证 i 是递增搜索的。

代码

[sol1-C++]

class Solution {
private:
    int digit[100];

public:
    long long kMirror(int k, int n) {
        auto isPalindrome = [&](long long x) -> bool {
            int length = -1;
            while (x) {
                ++length;
                digit[length] = x % k;
                x /= k;
            }
            for (int i = 0, j = length; i < j; ++i, --j) {
                if (digit[i] != digit[j]) {
                    return false;
                }
            }
            return true;
        };

        int left = 1, count = 0;
        long long ans = 0;
        while (count < n) {
            int right = left * 10;
            // op = 0 表示枚举奇数长度回文，op = 1 表示枚举偶数长度回文
            for (int op = 0; op < 2; ++op) {
                // 枚举 i'
                for (int i = left; i < right && count < n; ++i) {
                    long long combined = i;
                    int x = (op == 0 ? i / 10 : i);
                    while (x) {
                        combined = combined * 10 + x % 10;
                        x /= 10;
                    }
                    if (isPalindrome(combined)) {
                        ++count;
                        ans += combined;
                    }
                }
            }
            left = right;
        }
        return ans;
    }
};

[sol1-Python3]

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def isPalindrome(x: int) -> bool:
            digit = list()
            while x:
                digit.append(x % k)
                x //= k
            return digit == digit[::-1]

        left, cnt, ans = 1, 0, 0
        while cnt < n:
            right = left * 10
            # op = 0 表示枚举奇数长度回文，op = 1 表示枚举偶数长度回文
            for op in [0, 1]:
                # 枚举 i'
                for i in range(left, right):
                    if cnt == n:
                        break
                    
                    combined = i
                    x = (i // 10 if op == 0 else i)
                    while x:
                        combined = combined * 10 + x % 10
                        x //= 10
                    if isPalindrome(combined):
                        cnt += 1
                        ans += combined
            left = right
        
        return ans

复杂度分析

对于给定的 n 和 k，我们很难找出第 n 个 k 镜像数字的范围。对于本题而言，最坏情况下为 n = 30，k = 7，对应的数为 64454545446，因此我们期望搜索的范围为 O(10^5)。

方法二：预处理

思路与算法

我们可以预处理出 k = 2, 3, \cdots, 9 的前 30 个 k 镜像数字，并直接累加返回答案。

代码

[sol2-C++]

class Solution {
private:
    static constexpr long long ans[][30] = {
        {1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939},
        {1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138},
        {1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715},
        {1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121},
        {1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654},
        {1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446},
        {1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355},
        {1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442}
    };

public:
    long long kMirror(int k, int n) {
        return accumulate(ans[k - 2], ans[k - 2] + n, 0LL);
    }
};

[sol2-Python3]

class Solution:

    ANS = [
            [1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939],
            [1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138],
            [1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715],
            [1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121],
            [1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654],
            [1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446],
            [1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355],
            [1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442],
        ]

    def kMirror(self, k: int, n: int) -> int:
        return sum(Solution.ANS[k - 2][:n])