Welcome to Subscribe On Youtube
2081. Sum of k-Mirror Numbers
Description
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
Solutions
-
class Solution { public long kMirror(int k, int n) { long ans = 0; for (int l = 1;; ++l) { int x = (int) Math.pow(10, (l - 1) / 2); int y = (int) Math.pow(10, (l + 1) / 2); for (int i = x; i < y; i++) { long v = i; for (int j = l % 2 == 0 ? i : i / 10; j > 0; j /= 10) { v = v * 10 + j % 10; } String ss = Long.toString(v, k); if (check(ss.toCharArray())) { ans += v; if (--n == 0) { return ans; } } } } } private boolean check(char[] c) { for (int i = 0, j = c.length - 1; i < j; i++, j--) { if (c[i] != c[j]) { return false; } } return true; } }
-
class Solution { public: long long kMirror(int k, int n) { long long ans = 0; for (int l = 1;; ++l) { int x = pow(10, (l - 1) / 2); int y = pow(10, (l + 1) / 2); for (int i = x; i < y; ++i) { long long v = i; int j = (l % 2 == 0) ? i : i / 10; while (j > 0) { v = v * 10 + j % 10; j /= 10; } if (check(v, k)) { ans += v; if (--n == 0) { return ans; } } } } } private: bool check(long long x, int k) { vector<int> s; while (x > 0) { s.push_back(x % k); x /= k; } for (int i = 0, j = s.size() - 1; i < j; ++i, --j) { if (s[i] != s[j]) { return false; } } return true; } };
-
class Solution: def kMirror(self, k: int, n: int) -> int: def check(x: int, k: int) -> bool: s = [] while x: s.append(x % k) x //= k return s == s[::-1] ans = 0 for l in count(1): x = 10 ** ((l - 1) // 2) y = 10 ** ((l + 1) // 2) for i in range(x, y): v = i j = i if l % 2 == 0 else i // 10 while j > 0: v = v * 10 + j % 10 j //= 10 if check(v, k): ans += v n -= 1 if n == 0: return ans
-
func kMirror(k int, n int) int64 { check := func(x int64, k int) bool { s := []int{} for x > 0 { s = append(s, int(x%int64(k))) x /= int64(k) } for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { if s[i] != s[j] { return false } } return true } var ans int64 = 0 for l := 1; ; l++ { x := pow10((l - 1) / 2) y := pow10((l + 1) / 2) for i := x; i < y; i++ { v := int64(i) j := i if l%2 != 0 { j = i / 10 } for j > 0 { v = v*10 + int64(j%10) j /= 10 } if check(v, k) { ans += v n-- if n == 0 { return ans } } } } } func pow10(exp int) int { res := 1 for i := 0; i < exp; i++ { res *= 10 } return res }
-
function kMirror(k: number, n: number): number { function check(x: number, k: number): boolean { const s: number[] = []; while (x > 0) { s.push(x % k); x = Math.floor(x / k); } for (let i = 0, j = s.length - 1; i < j; i++, j--) { if (s[i] !== s[j]) { return false; } } return true; } let ans = 0; for (let l = 1; ; l++) { const x = Math.pow(10, Math.floor((l - 1) / 2)); const y = Math.pow(10, Math.floor((l + 1) / 2)); for (let i = x; i < y; i++) { let v = i; let j = l % 2 === 0 ? i : Math.floor(i / 10); while (j > 0) { v = v * 10 + (j % 10); j = Math.floor(j / 10); } if (check(v, k)) { ans += v; n--; if (n === 0) { return ans; } } } } }