{"id":3952,"date":"2018-09-13T23:18:07","date_gmt":"2018-09-14T06:18:07","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3952"},"modified":"2018-09-20T22:39:10","modified_gmt":"2018-09-21T05:39:10","slug":"leetcode-902-numbers-at-most-n-given-digit-set","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-902-numbers-at-most-n-given-digit-set\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 902. Numbers At Most N Given Digit Set"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 902. Numbers At Most N Given Digit Set - \u5237\u9898\u627e\u5de5\u4f5c EP225\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/d2O_jwPxroc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1><strong>Problem<\/strong><\/h1>\n<p>We have a\u00a0<strong>sorted<\/strong>\u00a0set of digits\u00a0<code>D<\/code>, a non-empty subset of\u00a0<code>{'1','2','3','4','5','6','7','8','9'}<\/code>.\u00a0 (Note that\u00a0<code>'0'<\/code>\u00a0is not included.)<\/p>\n<p>Now, we write numbers using these digits, using each digit as many times as we want.\u00a0 For example, if\u00a0<code>D = {'1','3','5'}<\/code>, we may write numbers such as\u00a0<code>'13', '551', '1351315'<\/code>.<\/p>\n<p>Return the number of positive integers that can be written (using the digits of\u00a0<code>D<\/code>) that are less than or equal to\u00a0<code>N<\/code>.<\/p>\n<p><strong>Example 1:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>D = <span id=\"example-input-1-1\">[\"1\",\"3\",\"5\",\"7\"]<\/span>, N = <span id=\"example-input-1-2\">100<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-1\">20<\/span>\r\n<strong>Explanation: <\/strong>\r\nThe 20 numbers that can be written are:\r\n1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.\r\n<\/pre>\n<div>\n<p><strong>Example 2:<\/strong><\/p>\n<pre class=\"crayon:false\"><strong>Input: <\/strong>D = <span id=\"example-input-2-1\">[\"1\",\"4\",\"9\"]<\/span>, N = <span id=\"example-input-2-2\">1000000000<\/span>\r\n<strong>Output: <\/strong><span id=\"example-output-2\">29523<\/span>\r\n<strong>Explanation: <\/strong>\r\nWe can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,\r\n81 four digit numbers, 243 five digit numbers, 729 six digit numbers,\r\n2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.\r\nIn total, this is 29523 integers that can be written using the digits of D.<\/pre>\n<\/div>\n<p><strong>Note:<\/strong><\/p>\n<ol>\n<li><code>D<\/code>\u00a0is a\u00a0subset of digits\u00a0<code>'1'-'9'<\/code>\u00a0in sorted order.<\/li>\n<li><code>1 &lt;= N &lt;= 10^9<\/code><\/li>\n<\/ol>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-4064\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/902-ep225.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/902-ep225.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/902-ep225-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2018\/09\/902-ep225-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/p>\n<h1><strong>Solution -1: DFS (TLE)<\/strong><\/h1>\n<p>Time complexity: O(|D|^log10(N))<\/p>\n<p>Space complexity: O(n)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  int atMostNGivenDigitSet(vector&lt;string&gt;&amp; D, int N) {\r\n    int ans = 0;    \r\n    dfs(D, 0, N, ans);\r\n    return ans;\r\n  }\r\nprivate:\r\n  void dfs(const vector&lt;string&gt;&amp; D, int cur, int N, int&amp; ans) {\r\n    if (cur &gt; N) return;\r\n    if (cur &gt; 0 &amp;&amp; cur &lt;= N) ++ans;\r\n    for (const string&amp; d : D)      \r\n      dfs(D, cur * 10 + d[0] - '0', N, ans);    \r\n  }\r\n};<\/pre>\n<h1><strong>Solution 1: Math<\/strong><\/h1>\n<p>Time complexity: O(log10(N))<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>Suppose N has n digits.<\/p>\n<h3>less than n digits<\/h3>\n<p>We can use all the numbers from D to construct numbers of with length 1,2,&#8230;,n-1 which are guaranteed to be less than N.<\/p>\n<p>e.g. n = 52125, D = [1, 2, 5]<\/p>\n<p>format X: e.g. 1, 2, 5 counts = |D| ^ 1<\/p>\n<p>format XX: e.g. 11,12,15,21,22,25,51,52,55, counts = |D|^2<\/p>\n<p>format XXX:\u00a0 counts = |D|^3<\/p>\n<p>format XXXX: counts = |D|^4<\/p>\n<h3>exact n digits<\/h3>\n<p>if all numbers in D\u00a0 != N[0], counts = |d &lt; N[0] | d in D| * |D|^(n-1), and we are done.<\/p>\n<p>e.g. N = 34567, D = [1,2,8]<\/p>\n<p>we can make:<\/p>\n<ul>\n<li>X |3|^1<\/li>\n<li>XX |3| ^ 2<\/li>\n<li>XXX |3| ^ 3<\/li>\n<li>XXXX |3| ^ 3<\/li>\n<li>1XXXX, |3|^4<\/li>\n<li>2XXXX, |3|^4<\/li>\n<li>we can&#8217;t do 8XXXX<\/li>\n<\/ul>\n<p>Total = (3^1 + 3^2 + 3^3 + 3^4) + 2 * |3|^ 4 = 120 + 162 = 282<\/p>\n<p>N = 52525, D = [1,2,5]<\/p>\n<p>However, if d = N[i], we need to check the next digit&#8230;<\/p>\n<ul>\n<li>X |3|^1<\/li>\n<li>XX |3| ^ 2<\/li>\n<li>XXX |3| ^ 3<\/li>\n<li>XXXX |3| ^ 3<\/li>\n<li>1XXXX, |3|^4<\/li>\n<li>2XXXX, |3|^4<\/li>\n<li>\u00a0<span style=\"color: #ff0000;\"><strong>5<\/strong><\/span>????\n<ul>\n<li><span style=\"color: #ff0000;\"><strong>5<\/strong><\/span>1XXX |3|^3<\/li>\n<li><span style=\"color: #ff0000;\"><strong>52<\/strong><\/span>???\n<ul>\n<li><span style=\"color: #ff0000;\"><strong>52<\/strong><\/span>1XX |3|^2<\/li>\n<li><span style=\"color: #ff0000;\"><strong>52<\/strong><\/span>2XX |3|^2<\/li>\n<li><span style=\"color: #ff0000;\"><strong>525<\/strong><\/span>??\n<ul>\n<li><span style=\"color: #ff0000;\"><strong>525<\/strong><\/span>1X |3|^1<\/li>\n<li><span style=\"color: #ff0000;\"><strong>5252<\/strong><\/span>?\n<ul>\n<li><span style=\"color: #ff0000;\"><strong>5252<\/strong><\/span>1 |3|^0<\/li>\n<li><span style=\"color: #ff0000;\"><strong>5252<\/strong><\/span>2 |3|^0<\/li>\n<li><span style=\"color: #ff0000;\"><strong>52525<\/strong><\/span>\u00a0+1<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>total = (120) + 2 * |3|^4 + |3|^3 + 2*|3|^2 + |3|^1 + 2 * |3|^0 + 1 = 120 + 213 = 333<\/p>\n<p>if every digit of N is from D, then we also have a valid solution, thus need to + 1.<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">class Solution {\r\npublic:\r\n  int atMostNGivenDigitSet(vector&lt;string&gt;&amp; D, int N) {\r\n    const string s = to_string(N);\r\n    const int n = s.length();\r\n    int ans = 0;\r\n    for (int i = 1; i &lt; n; ++i)\r\n      ans += pow(D.size(), i);\r\n    \r\n    for (int i = 0; i &lt; n; ++i) {\r\n      bool prefix = false;\r\n      for (const string&amp; d : D) {\r\n        if (d[0] &lt; s[i]) {\r\n          ans += pow(D.size(), n - i - 1);\r\n        } else if (d[0] == s[i]) {\r\n          prefix = true;\r\n          break;\r\n        }\r\n      }\r\n      if (!prefix) return ans;\r\n    }\r\n    \r\n    \/\/ plus one for solution N itself, all the digits are from D.\r\n    return ans + 1;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:java decode:true \">\/\/ Author: Huahua, 4 ms\r\nclass Solution {\r\n  public int atMostNGivenDigitSet(String[] D, int N) {\r\n    char[] s = String.valueOf(N).toCharArray();\r\n    int n = s.length;\r\n    int ans = 0;\r\n    for (int i = 1; i &lt; n; ++i)\r\n      ans += (int)Math.pow(D.length, i);\r\n    for (int i = 0; i &lt; n; ++i) {\r\n      boolean prefix = false;\r\n      for (String d : D) {\r\n        if (d.charAt(0) &lt; s[i]) {\r\n          ans += Math.pow(D.length, n - i - 1);\r\n        } else if (d.charAt(0) == s[i]) {\r\n          prefix = true;\r\n          break;\r\n        }\r\n      }\r\n      if (!prefix) return ans;\r\n    }\r\n    return ans + 1;\r\n  }\r\n}<\/pre>\n<p>&nbsp;<\/p>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:python decode:true \"># Author: Huahua, 36 ms\r\nclass Solution:\r\n  def atMostNGivenDigitSet(self, D, N):\r\n    s = str(N)\r\n    n = len(s)\r\n    ans = sum(len(D) ** i for i in range(1, n))\r\n    for i, c in enumerate(s):\r\n      ans += len(D) ** (n - i - 1) * sum(d &lt; c for d in D)\r\n      if c not in D: return ans\r\n    return ans + 1<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Problem We have a\u00a0sorted\u00a0set of digits\u00a0D, a non-empty subset of\u00a0{&#8216;1&#8242;,&#8217;2&#8242;,&#8217;3&#8242;,&#8217;4&#8242;,&#8217;5&#8242;,&#8217;6&#8242;,&#8217;7&#8242;,&#8217;8&#8242;,&#8217;9&#8217;}.\u00a0 (Note that\u00a0&#8216;0&#8217;\u00a0is not included.) Now, we write numbers using these digits, using each digit as&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[122,217,31],"class_list":["post-3952","post","type-post","status-publish","format-standard","hentry","category-math","tag-combination","tag-hard","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3952","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=3952"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3952\/revisions"}],"predecessor-version":[{"id":4065,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3952\/revisions\/4065"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3952"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3952"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}