{"id":3196,"date":"2018-07-16T08:14:53","date_gmt":"2018-07-16T15:14:53","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3196"},"modified":"2018-07-16T08:15:17","modified_gmt":"2018-07-16T15:15:17","slug":"leetcode-357-count-numbers-with-unique-digits","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-357-count-numbers-with-unique-digits\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 357. Count Numbers with Unique Digits"},"content":{"rendered":"<h1><strong>Problem<\/strong><\/h1>\n<p>Given a\u00a0<b>non-negative<\/b>\u00a0integer n, count all numbers with unique digits, x, where 0 \u2264 x &lt; 10<sup>n<\/sup>.<\/p>\n<p><b>Example:<\/b><br \/>\nGiven n = 2, return 91. (The answer should be the total numbers in the range of 0 \u2264 x &lt; 100, excluding\u00a0<code>[11,22,33,44,55,66,77,88,99]<\/code>)<\/p>\n<h1><strong>Solution: Math<\/strong><\/h1>\n<p>f(0) = 1 (0)<\/p>\n<p>f(1) = 10 (0 &#8211; 9)<\/p>\n<p>f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))<\/p>\n<p>f(3) = 9 * 9 * 8<\/p>\n<p>f(4) = 9 * 9 * 8 * 7<\/p>\n<p>&#8230;<\/p>\n<p>f(x) = 0 if x &gt;= 10<\/p>\n<p>ans = sum(f[1] ~ f[n])<\/p>\n<p>Time complexity: O(1)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n  int countNumbersWithUniqueDigits(int n) {\r\n    if (n == 0) return 1;\r\n    vector&lt;int&gt; f(11);    \r\n    f[1] = 10;\r\n    f[2] = 9 * 9;\r\n    for (int i = 3; i &lt;= 10; ++i)\r\n      f[i] = f[i - 1] * (10 - i + 1);\r\n    int ans = 0;\r\n    for (int i = 0; i &lt;= min(10, n); ++i)\r\n      ans += f[i];\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given a\u00a0non-negative\u00a0integer n, count all numbers with unique digits, x, where 0 \u2264 x &lt; 10n. Example: Given n = 2, return 91. (The&#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":[31,177,121,339],"class_list":["post-3196","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","tag-permutation","tag-production","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3196","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=3196"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3196\/revisions"}],"predecessor-version":[{"id":3198,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3196\/revisions\/3198"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3196"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}