aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--sum_k_mirror_num.c60
-rw-r--r--sum_k_mirror_num.py277
2 files changed, 337 insertions, 0 deletions
diff --git a/sum_k_mirror_num.c b/sum_k_mirror_num.c
new file mode 100644
index 0000000..84f55f1
--- /dev/null
+++ b/sum_k_mirror_num.c
@@ -0,0 +1,60 @@
+// 2081. Sum of k-Mirror Numbers
+#include "leetcode.h"
+
+/*
+ * 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. given the base
+ * 'k' and the number 'n', return the sum of the 'n' smallest k-mirror numbers.
+ */
+
+long long kMirror(int k, int n) {
+ 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}};
+ long long sum = 0;
+ for (int i = 0; i < n; i++)
+ sum += ans[k - 2][i];
+ return sum;
+}
+
+int main() {
+ printf("%lld\n", kMirror(2, 5)); // expect: 25
+ printf("%lld\n", kMirror(3, 7)); // expect: 499
+ printf("%lld\n", kMirror(7, 17)); // expect: 20379000
+}
diff --git a/sum_k_mirror_num.py b/sum_k_mirror_num.py
new file mode 100644
index 0000000..5b35e59
--- /dev/null
+++ b/sum_k_mirror_num.py
@@ -0,0 +1,277 @@
+# 2081. Sum of k-Mirror Numbers
+
+
+class Solution(object):
+ def kMirror(self, k, n):
+ """
+ :type k: int
+ :type n: int
+ :rtype: int
+ """
+ return (
+ [
+ [
+ 1,
+ 4,
+ 9,
+ 16,
+ 25,
+ 58,
+ 157,
+ 470,
+ 1055,
+ 1772,
+ 9219,
+ 18228,
+ 33579,
+ 65802,
+ 105795,
+ 159030,
+ 212865,
+ 286602,
+ 872187,
+ 2630758,
+ 4565149,
+ 6544940,
+ 9674153,
+ 14745858,
+ 20005383,
+ 25846868,
+ 39347399,
+ 759196316,
+ 1669569335,
+ 2609044274,
+ ],
+ [
+ 1,
+ 3,
+ 7,
+ 15,
+ 136,
+ 287,
+ 499,
+ 741,
+ 1225,
+ 1881,
+ 2638,
+ 31730,
+ 80614,
+ 155261,
+ 230718,
+ 306985,
+ 399914,
+ 493653,
+ 1342501,
+ 2863752,
+ 5849644,
+ 9871848,
+ 14090972,
+ 18342496,
+ 22630320,
+ 28367695,
+ 36243482,
+ 44192979,
+ 71904751,
+ 155059889,
+ ],
+ [
+ 1,
+ 3,
+ 6,
+ 11,
+ 66,
+ 439,
+ 832,
+ 1498,
+ 2285,
+ 3224,
+ 11221,
+ 64456,
+ 119711,
+ 175366,
+ 233041,
+ 739646,
+ 2540727,
+ 4755849,
+ 8582132,
+ 12448815,
+ 17500320,
+ 22726545,
+ 27986070,
+ 33283995,
+ 38898160,
+ 44577925,
+ 98400760,
+ 721411086,
+ 1676067545,
+ 53393239260,
+ ],
+ [
+ 1,
+ 3,
+ 6,
+ 10,
+ 16,
+ 104,
+ 356,
+ 638,
+ 1264,
+ 1940,
+ 3161,
+ 18912,
+ 37793,
+ 10125794,
+ 20526195,
+ 48237967,
+ 78560270,
+ 126193944,
+ 192171900,
+ 1000828708,
+ 1832161846,
+ 2664029984,
+ 3500161622,
+ 4336343260,
+ 6849225412,
+ 9446112364,
+ 12339666346,
+ 19101218022,
+ 31215959143,
+ 43401017264,
+ ],
+ [
+ 1,
+ 3,
+ 6,
+ 10,
+ 15,
+ 22,
+ 77,
+ 188,
+ 329,
+ 520,
+ 863,
+ 1297,
+ 2074,
+ 2942,
+ 4383,
+ 12050,
+ 19827,
+ 41849,
+ 81742,
+ 156389,
+ 325250,
+ 1134058,
+ 2043967,
+ 3911648,
+ 7009551,
+ 11241875,
+ 15507499,
+ 19806423,
+ 24322577,
+ 28888231,
+ ],
+ [
+ 1,
+ 3,
+ 6,
+ 10,
+ 15,
+ 21,
+ 29,
+ 150,
+ 321,
+ 563,
+ 855,
+ 17416,
+ 83072,
+ 2220384,
+ 6822448,
+ 13420404,
+ 20379000,
+ 29849749,
+ 91104965,
+ 321578997,
+ 788407661,
+ 1273902245,
+ 1912731081,
+ 2570225837,
+ 3428700695,
+ 29128200347,
+ 69258903451,
+ 115121130305,
+ 176576075721,
+ 241030621167,
+ ],
+ [
+ 1,
+ 3,
+ 6,
+ 10,
+ 15,
+ 21,
+ 28,
+ 37,
+ 158,
+ 450,
+ 783,
+ 1156,
+ 1570,
+ 2155,
+ 5818,
+ 14596,
+ 27727,
+ 41058,
+ 67520,
+ 94182,
+ 124285,
+ 154588,
+ 362290,
+ 991116,
+ 1651182,
+ 3148123,
+ 5083514,
+ 7054305,
+ 11253219,
+ 66619574,
+ ],
+ [
+ 1,
+ 3,
+ 6,
+ 10,
+ 15,
+ 21,
+ 28,
+ 36,
+ 227,
+ 509,
+ 882,
+ 1346,
+ 1901,
+ 2547,
+ 3203,
+ 10089,
+ 35841,
+ 63313,
+ 105637,
+ 156242,
+ 782868,
+ 2323319,
+ 4036490,
+ 5757761,
+ 7586042,
+ 9463823,
+ 11349704,
+ 13750746,
+ 16185088,
+ 18627530,
+ ],
+ ]
+ )[k - 2][n - 1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kMirror(k=2, n=5))
+ print(obj.kMirror(k=3, n=7))
+ print(obj.kMirror(k=7, n=17))