Let f(x)
be the number of zeroes at the end of x!
. (Recall that x! = 1 * 2 * 3 * ... * x
, and by convention, 0! = 1
.)
For example, f(3) = 0
because 3! = 6 has no zeroes at the end, while f(11) = 2
because 11! = 39916800 has 2 zeroes at the end. Given K
, find how many non-negative integers x
have the property that f(x) = K
.
1 2 3 4 5 6 7 8 9 |
Example 1: Input: K = 0 Output: 5 Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes. Example 2: Input: K = 5 Output: 0 Explanation: There is no x such that x! ends in K = 5 zeroes. |
Note:
K
will be an integer in the range[0, 10^9]
.
Idea:
First we need to compute how many trailing zeros n! has.
See 花花酱 LeetCode 172. Factorial Trailing Zeroes for details
It’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 – 1 using binary search.
Then we know that are exact p numbers 1,2,…,p whose trailing zeros are less or equal to K.
And exact q numbers 1, 2, …, q whose trailing zeros are less or equal to K – 1.
q + 1, q + 2, …, m (m – q numbers in total) the numbers with trailing zeros equal to K.
Solution 1: Math + Binary Search
Time complexity: O(log2(INT_MAX)*log5(INT_MAX))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Running time: 3 ms class Solution { public: int preimageSizeFZF(int K) { return g(K) - g(K - 1); } private: // Find the largest number l, that numZeros(l!) == K and numZeros((l+1)!) > K int g(int K) { int l = 0; int r = INT_MAX; while (l < r) { int m = l + (r - l) / 2; int zeros = numZeros(m); if (zeros <= K) l = m + 1; else r = m; } return l; } int numZeros(int n) { return n < 5 ? 0 : n / 5 + numZeros(n / 5); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
官方solution对int l int r 的初始值范围限定更小。int l=K,int r=10*K+1.可是我没看懂它是怎么得出来的。。。