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,
9is a 2-mirror number. The representation of9in base-10 and base-2 are9and1001respectively, which read the same both forward and backward. - On the contrary,
4is not a 2-mirror number. The representation of4in 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 <= 91 <= n <= 30
Solution: Generate palindromes in base-k.
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Author: Huahua class Solution: def kMirror(self, k: int, n: int) -> int: def getNext(x: str) -> str: s = list(x) l = len(s) for i in range(l // 2, l): if int(s[i]) + 1 >= k: continue s[i] = s[~i] = str(int(s[i]) + 1) for j in range(l // 2, i): s[j] = s[~j] = "0" return "".join(s) return "1" + "0" * (l - 1) + "1" ans = 0 x = "0" for _ in range(n): while True: x = getNext(x) val = int(x, k) if str(val) == str(val)[::-1]: break ans += val return ans |