{"id":1944,"date":"2018-03-04T00:01:23","date_gmt":"2018-03-04T08:01:23","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1944"},"modified":"2018-03-06T21:45:01","modified_gmt":"2018-03-07T05:45:01","slug":"leetcode-793-preimage-size-of-factorial-zeroes-function","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-793-preimage-size-of-factorial-zeroes-function\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 793. Preimage Size of Factorial Zeroes Function"},"content":{"rendered":"<p>Let\u00a0<code>f(x)<\/code>\u00a0be the number of zeroes at the end of\u00a0<code>x!<\/code>. (Recall that\u00a0<code>x! = 1 * 2 * 3 * ... * x<\/code>, and by convention,\u00a0<code>0! = 1<\/code>.)<\/p>\n<p>For example,\u00a0<code>f(3) = 0<\/code>\u00a0because 3! = 6 has no zeroes at the end, while\u00a0<code>f(11) = 2<\/code>\u00a0because 11! = 39916800 has 2 zeroes at the end. Given\u00a0<code>K<\/code>, find how many non-negative integers\u00a0<code>x<\/code>\u00a0have the property that\u00a0<code>f(x) = K<\/code>.<\/p>\n<pre class=\"\">Example 1:\r\nInput: K = 0\r\nOutput: 5\r\nExplanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.\r\n\r\nExample 2:\r\nInput: K = 5\r\nOutput: 0\r\nExplanation: There is no x such that x! ends in K = 5 zeroes.\r\n<\/pre>\n<p><strong>Note:<\/strong><\/p>\n<ul>\n<li><code>K<\/code>\u00a0will be an integer in the range\u00a0<code>[0, 10^9]<\/code>.<\/li>\n<\/ul>\n<p><strong>Idea:<\/strong><\/p>\n<p>First we need to compute how many trailing zeros n! has.<\/p>\n<p>See \u00a0<a href=\"http:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-172-factorial-trailing-zeroes\/\">\u82b1\u82b1\u9171 LeetCode 172. Factorial Trailing Zeroes<\/a> for details<\/p>\n<p>It&#8217;s hard to say how many numbers have trailing zeros equals to K, but we can find the largest number p whose trailing zeros is K using binary search. (p+1)! has more than K trailing zeros. And do the same thing to find the largest number q whose trailing zeros is K &#8211; 1 using binary search.<\/p>\n<p>Then we know that are exact p numbers 1,2,&#8230;,p whose trailing zeros are less or equal to K.<\/p>\n<p>And exact q numbers 1, 2, &#8230;, q whose trailing zeros are less or equal to K &#8211; 1.<\/p>\n<p>q + 1, q + 2, &#8230;, m (m &#8211; q numbers in total) the numbers with trailing zeros equal to K.<\/p>\n<p><strong>Solution 1: Math + Binary Search<\/strong><\/p>\n<p>Time complexity: O(log2(INT_MAX)*log5(INT_MAX))<\/p>\n<p>Space complexity: O(1)<\/p>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true  \">\/\/ Author: Huahua\r\n\/\/ Running time: 3 ms\r\nclass Solution {\r\npublic:\r\n  int preimageSizeFZF(int K) {\r\n    return g(K) - g(K - 1);\r\n  }\r\nprivate:\r\n  \/\/ Find the largest number l, that numZeros(l!) == K and numZeros((l+1)!) &gt; K\r\n  int g(int K) {    \r\n    int l = 0;\r\n    int r = INT_MAX;\r\n    while (l &lt; r) {\r\n      int m = l + (r - l) \/ 2;\r\n      int zeros = numZeros(m);\r\n      if (zeros &lt;= K)\r\n        l = m + 1;\r\n      else\r\n        r = m;\r\n    }    \r\n    return l;\r\n  }\r\n  \r\n  int numZeros(int n) {\r\n    return n &lt; 5 ? 0 : n \/ 5 + numZeros(n \/ 5);\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Let\u00a0f(x)\u00a0be the number of zeroes at the end of\u00a0x!. (Recall that\u00a0x! = 1 * 2 * 3 * &#8230; * x, and by convention,\u00a00! =&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149,49],"tags":[230,217,231],"class_list":["post-1944","post","type-post","status-publish","format-standard","hentry","category-binary-search","category-math","tag-factorial","tag-hard","tag-zeros","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1944","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=1944"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1944\/revisions"}],"predecessor-version":[{"id":2004,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/1944\/revisions\/2004"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=1944"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=1944"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=1944"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}