diff options
author | Jack Sangdahl <[email protected]> | 2025-06-22 18:18:26 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-22 18:18:26 -0600 |
commit | eeb84a6833e37c84f3fc95f533b749a60f894877 (patch) | |
tree | 59a096b19f6f1a7c413c4e68266ec37834077045 | |
parent | 4295d35ad283c079cd30f131bda21c3dd5d49896 (diff) | |
download | leetcode-eeb84a6833e37c84f3fc95f533b749a60f894877.tar.gz leetcode-eeb84a6833e37c84f3fc95f533b749a60f894877.zip |
2081. sum of k-mirror numbers
-rw-r--r-- | sum_k_mirror_num.c | 60 | ||||
-rw-r--r-- | sum_k_mirror_num.py | 277 |
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)) |