Given an integer n, return the number of trailing zeroes in n!.
Note: Your solution should be in logarithmic time complexity.
Solution:
As we know trailing zeroes are led by multiplying 10, which is 5*2. Clearly occurrences of factor 2 is much higher than of factor 5 in n! So calculating trailing zeros in n! actually calculating how many factor 5 in n! . For example,5,10,15,20 have one factor 5 each while for 25,50,75,100 each of them has two factor 5. So for example when we try to find the trailing zeros of 32! We know it will have 1(5)+1(10)+1(15)+1(20)+2(25)=6 trailing zeros.So the equation is(n/5+n/(5^2)+n/(5^3)...)
public int trailingZeroes(int n) {
if(n<5) return 0;
int res=0;
while(n>=5){
res+=n/5;
n=n/5;
}
return res;
}
No comments:
Post a Comment