Note: Your solution should be in logarithmic time complexity.
Idea: Only five*even number can produce 0's. Since there are plenty of even numbers in the factorial, the only problem is to find how many 5's are contained in the items of the factorial. For example, when n=75:
1) At least one 5: 5,10,15,20,25,30,35,40,45,50,55,60,65,70,75.
2) At least two 5's: 25, 50, 75.
3) At least three 5's: N/A.
The total number of 5's is 15+3=18. Since 25, 50, 70 have been counted once in at least one 5, we just need to add the number of items in each category.
So the equation to calculate the number of 5's is:
result=n/5+n/(5^2)+n/(5^3)+n/(5^4)+.... until n<5^x. All the number in the equation are integers, so "/" = "/ and floor".
Time: O(lgn) Space:O(1)
Code:
public class Solution {
public int trailingZeroes(int n) {
int sum=0;
long product=5;
long number=n;
while(number>=product)
{
sum+=(int)(number/product);
product=product*5;
}
return sum;
}
}
No comments:
Post a Comment