[LeetCode]172

// 172fact_trail_zero.cpp

#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <windows.h>
/*
 = a*10^k = a* (5^k*2^k)
*/

int trailingZeroes0(int n)
{
   int sum=0;
   int i;
   for(i=1;i<=n;i++){
      int x=i;
      while(x%5==0){
         x/=5;
         sum++;
      }
   }
   return sum;
}


int trailingZeroes1(int n)
{
   int sum=0;
   int i;
   for(i=5;i<=n;i+=5){
      int x=i;
      while(x%5==0){
         x/=5;
         sum++;
      }
   }
   return sum;
}
/*
5 10 15 20 25 30 35 小于等于35的数当中有多少5的倍数？ 答案是35/5 = 7
1  2  3  4  5  6  7
*/
int trailingZeroes2(int n)
{
   int sum=0;
   int i;
   while(n>0){
      sum+=n/5;
      n/=5;
   }
   return sum;
}

int trailingZeroes3(int n)
{
   return n == 0 ? 0 : n / 5 + trailingZeroes3(n / 5);
}

int main(int argc, char* argv[])
{
   int n;
   int oput;
   int t;
   scanf("%d",&n);
   do{
      t=GetTickCount();
      oput=trailingZeroes0(n);
      t=GetTickCount()-t;
      printf("0st func time %dms, Trailing zeroes is %d\n",t,oput);
      t=GetTickCount();
      oput=trailingZeroes1(n);
      t=GetTickCount()-t;
      printf("1st func time %dms, Trailing zeroes is %d\n",t,oput);
      t=GetTickCount();
      oput=trailingZeroes2(n);
      t=GetTickCount()-t;
      printf("2nd func time %dms, Trailing zeroes is %d\n",t,oput);
      t=GetTickCount();
      oput=trailingZeroes3(n);
      t=GetTickCount()-t;
      printf("3nd func time %dms, Trailing zeroes is %d\n",t,oput);
      scanf("%d",&n);
   }while(n!=0);
   return 0;
}

/*
1808548329
10
*/

1999999999
0st func time 9812ms, Trailing zeroes is 499999988
1st func time 4321ms, Trailing zeroes is 499999988
2nd func time 0ms, Trailing zeroes is 499999988
3nd func time 0ms, Trailing zeroes is 499999988