leecode 解题总结：172. Factorial Trailing Zeroes

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:Given an integer n, return the number of trailing zeroes in n!.Note: Your solution should be in logarithmic time complexity.分析:计算n!中尾部的0，时间复杂度必须是O(logN)尾部的0的计算因为阶乘中构成：肯定是因为2*5,阶乘就是=2^k * 5^p = 10^( min(k,p) )，所以0的个数=min(k,p)1,2,3,4,5,6,7,8,9,10,11,12,13,14,15又发现，5的个数总是少于2的个数，所以0的个数=5的个数决定5的个数n/5,20/5=4,15/5=3,25/5=525/5=5,125/5但是25发现5^2，有两个5需要弄清楚，需要计算n!=5^k * x，求出k即可,5^2,5^3,125/5=25,只需要求出5^k <= n,中的k,然后用n/25=p,用p+(k-1)*k/2即可那么问题的关键就是变成如何计算出: 5^k <= n，可以用二分法，5^1如果每次乘以5，太慢了，最好5^1,5^2,5^4,这种翻倍举例:9求3^k,那么3 < 9,变成2*3=6,发现,6<9,发现6*2 = 12 > 9，所以取,所以找到了，5^1,5^2，5^4，如果找到5^k=n,直接输出k,如果发现5^k > n ,5^(k/2)，然后尝试k/2到k中进行二分法125/5=25,25/5=5,不断累除5即可，20/5=50/5=10,50=5^2+1输入:5202512550200输出:146311249没有考虑到50和25一样也是5^2，中25=5^2*150=5^2*275=5^2*3100=5^2*4125=5^3250=5^3*2 假设为v1+1+1+1+4+4+4+4+124+设计算出的最大指数为k,其他系数为v。(k-1)*v + (k-2)*4 + ..+ 1*4假设k=3,余数v=12 + 4  = 6,125 / 5 = 25直接每次获取5,10,...5n这种来做，但是时间复杂度为O(n)200=5^2*2*2*2关键:leecode解法:https://leetcode.com/PRoblems/factorial-trailing-zeroes/?tab=Solutions不断让让n除以i的数量，i乘以5得到新的i，重复上述操作。这样就能将n^2,n^3这种带来的额外的5的次数累加进去*/class Solution {public:    int trailingZeroes(int n) {		int result = 0;		for(long long i = 5 ; n / i > 0 ; i *= 5)		{			result += (n/i);		}		return result;    }};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 int temp = solution.trailingZeroes(num);		 cout << temp << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}