87 lines
2.8 KiB
C++
87 lines
2.8 KiB
C++
// Source : https://oj.leetcode.com/problems/factorial-trailing-zeroes/
|
||
// Author : Hao Chen
|
||
// Date : 2014-12-30
|
||
|
||
/**********************************************************************************
|
||
*
|
||
* Given an integer n, return the number of trailing zeroes in n!.
|
||
*
|
||
* Note: Your solution should be in polynomial time complexity.
|
||
*
|
||
* Credits:Special thanks to @ts for adding this problem and creating all test cases.
|
||
*
|
||
**********************************************************************************/
|
||
|
||
/*
|
||
* The idea is:
|
||
*
|
||
* 1. The ZERO comes from 10.
|
||
* 2. The 10 comes from 2 x 5
|
||
* 3. And we need to account for all the products of 5 and 2. likes 4×5 = 20 ...
|
||
* 4. So, if we take all the numbers with 5 as a factor, we'll have way more than enough even numbers
|
||
* to pair with them to get factors of 10
|
||
*
|
||
* **Example One**
|
||
*
|
||
* How many multiples of 5 are between 1 and 23?
|
||
* There is 5, 10, 15, and 20, for four multiples of 5. Paired with 2's from the even factors,
|
||
* this makes for four factors of 10, so: **23! has 4 zeros**.
|
||
*
|
||
*
|
||
* **Example Two**
|
||
*
|
||
* How many multiples of 5 are there in the numbers from 1 to 100?
|
||
*
|
||
* because 100 ÷ 5 = 20, so, there are twenty multiples of 5 between 1 and 100.
|
||
*
|
||
* but wait, actually 25 is 5×5, so each multiple of 25 has an extra factor of 5,
|
||
* ( e.g. 25 × 4 = 100，which introduces extra of zero )
|
||
*
|
||
* So, we need know how many multiples of 25 are between 1 and 100? Since 100 ÷ 25 = 4,
|
||
* (there are four multiples of 25 between 1 and 100)
|
||
*
|
||
* Finally, we get 20 + 4 = 24 trailing zeroes in 100!
|
||
*
|
||
*
|
||
* The above example tell us, we need care about 5, 5×5, 5×5×5, 5×5×5×5 ....
|
||
*
|
||
* **Example Three**
|
||
*
|
||
*
|
||
* 5^1 : 4617 ÷ 5 = 923.4, so we get 923 factors of 5
|
||
* 5^2 : 4617 ÷ 25 = 184.68, so we get 184 additional factors of 5
|
||
* 5^3 : 4617 ÷ 125 = 36.936, so we get 36 additional factors of 5
|
||
* 5^4 : 4617 ÷ 625 = 7.3872, so we get 7 additional factors of 5
|
||
* 5^5 : 4617 ÷ 3125 = 1.47744, so we get 1 more factor of 5
|
||
* 5^6 : 4617 ÷ 15625 = 0.295488, which is less than 1, so stop here.
|
||
*
|
||
* Then 4617! has 923 + 184 + 36 + 7 + 1 = 1151 trailing zeroes.
|
||
*
|
||
*/
|
||
|
||
|
||
class Solution {
|
||
public:
|
||
int trailingZeroes(int n) {
|
||
int result = 0;
|
||
//To avoid the integer overflow ( e.g. 'n >=1808548329' )
|
||
for(long long i=5; n/i>0 && i <= INT_MAX; i*=5){
|
||
result += (n/i);
|
||
}
|
||
return result;
|
||
}
|
||
|
||
// Alternative implementation which naturally avoid integer overflow issue.
|
||
int trailingZeroes(int n) {
|
||
int sum=0;
|
||
int tmp=0;
|
||
while(n/5>0)
|
||
{
|
||
tmp=n/5;
|
||
sum+=tmp;
|
||
n=tmp;
|
||
}
|
||
return sum;
|
||
}
|
||
};
|