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:
Kwill 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); } }; |