{"id":8758,"date":"2021-11-21T15:51:32","date_gmt":"2021-11-21T23:51:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8758"},"modified":"2021-11-21T15:52:49","modified_gmt":"2021-11-21T23:52:49","slug":"leetcode-2081-sum-of-k-mirror-numbers","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-2081-sum-of-k-mirror-numbers\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2081. Sum of k-Mirror Numbers"},"content":{"rendered":"\n<p>A&nbsp;<strong>k-mirror number<\/strong>&nbsp;is a&nbsp;<strong>positive<\/strong>&nbsp;integer&nbsp;<strong>without leading zeros<\/strong>&nbsp;that reads the same both forward and backward in base-10&nbsp;<strong>as well as<\/strong>&nbsp;in base-k.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example,&nbsp;<code>9<\/code>&nbsp;is a 2-mirror number. The representation of&nbsp;<code>9<\/code>&nbsp;in base-10 and base-2 are&nbsp;<code>9<\/code>&nbsp;and&nbsp;<code>1001<\/code>&nbsp;respectively, which read the same both forward and backward.<\/li><li>On the contrary,&nbsp;<code>4<\/code>&nbsp;is not a 2-mirror number. The representation of&nbsp;<code>4<\/code>&nbsp;in base-2 is&nbsp;<code>100<\/code>, which does not read the same both forward and backward.<\/li><\/ul>\n\n\n\n<p>Given the base&nbsp;<code>k<\/code>&nbsp;and the number&nbsp;<code>n<\/code>, return&nbsp;<em>the&nbsp;<strong>sum<\/strong>&nbsp;of the<\/em>&nbsp;<code>n<\/code>&nbsp;<em><strong>smallest<\/strong>&nbsp;k-mirror numbers<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> k = 2, n = 5\n<strong>Output:<\/strong> 25\n<strong>Explanation:\n<\/strong>The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:\n  base-10    base-2\n    1          1\n    3          11\n    5          101\n    7          111\n    9          1001\nTheir sum = 1 + 3 + 5 + 7 + 9 = 25. \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> k = 3, n = 7\n<strong>Output:<\/strong> 499\n<strong>Explanation:\n<\/strong>The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:\n  base-10    base-3\n    1          1\n    2          2\n    4          11\n    8          22\n    121        11111\n    151        12121\n    212        21212\nTheir sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> k = 7, n = 17\n<strong>Output:<\/strong> 20379000\n<strong>Explanation:<\/strong> The 17 smallest 7-mirror numbers are:\n1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= k &lt;= 9<\/code><\/li><li><code>1 &lt;= n &lt;= 30<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Generate palindromes in base-k.<\/strong><\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\"># Author: Huahua\nclass Solution:\n  def kMirror(self, k: int, n: int) -> int:\n    def getNext(x: str) -> str:\n      s = list(x)\n      l = len(s)    \n      for i in range(l \/\/ 2, l):\n        if int(s[i]) + 1 >= k: continue\n        s[i] = s[~i] = str(int(s[i]) + 1)\n        for j in range(l \/\/ 2, i): s[j] = s[~j] = \"0\"\n        return \"\".join(s)\n      return \"1\" + \"0\" * (l - 1) + \"1\"\n    ans = 0\n    x = \"0\"\n    for _ in range(n):\n      while True:\n        x = getNext(x)\n        val = int(x, k)\n        if str(val) == str(val)[::-1]: break\n      ans += val\n    return ans\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A&nbsp;k-mirror number&nbsp;is a&nbsp;positive&nbsp;integer&nbsp;without leading zeros&nbsp;that reads the same both forward and backward in base-10&nbsp;as well as&nbsp;in base-k. For example,&nbsp;9&nbsp;is a 2-mirror number. The representation of&nbsp;9&nbsp;in&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[217,727,42],"class_list":["post-8758","post","type-post","status-publish","format-standard","hentry","category-searching","tag-hard","tag-palindrom","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8758","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8758"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8758\/revisions"}],"predecessor-version":[{"id":8761,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8758\/revisions\/8761"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8758"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8758"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8758"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}