Friday, January 2, 2015

172. Factorial Trailing Zeroes LeetCode Java

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