【lintcode】2.尾部的零(c/c++/python解法）

古城微笑少年丶 2023-07-25 12:35 20阅读 0赞

# 题目 #

**设计一个算法，计算出n阶乘中尾部零的个数**  
**样例**  
**样例 1:**

输入: 11
    输出: 2
    样例解释: 
    11! = 39916800, 结尾的0有2个。

**样例 2:**

输入:  5
    输出: 1	
    样例解释: 
    5! = 120， 结尾的0有1个。

**挑战**  
**O(logN)的时间复杂度**

## 1.c++/c解法 ##

#### 第一次 ####

想法是通过向十取余来计算零的个数

class Solution { 
    public:
        /* * @param n: A long integer * @return: An integer, denote the number of trailing zeros in n! */
        long long trailingZeros(long long n) 
        { 
           
            int t=0,s=1;
            for(int i = 1 ;i <= n ; i++)
            { 
                s *= i;
            }
            while(s%10 == 0)
            { 
                t++;
                s /= 10;
            }
            return t;
        }
    };

第一次测试数据通过了，但是提交失败。测试数据达到12阶乘以上全部失败，而且运行时间超时。打算颠倒数字重头开始计算零的数字

long long trailingZeros(long long n)
        { 
    
            int t=0,s=1;
            int r[150000];
            for(int i = 1 ;i <= n ; i++)
            { 
                s *= i;
            }
            while(s != 0)
            { 
                r[t] = s % 10;
                t++;
                s /= 10;
            }
            int len = 0;
            for(;r[len]==0;len++)
            { 
                if(r[len]!=0)
                    break;
            }
            return len;
        }

再一次失败后觉得是数组长度问题，修改数组长度后还是错误。于是觉得是算法问题，不能用数组存放。于是直接每颠倒一位数字便进行判断：

long long trailingZeros(long long n)
        { 
    
            int t=0,s=1;
            for(int i = 1 ;i <= n ; i++)
            { 
                s *= i;
            }
            int len=0;
            while(s != 0)
            { 
                int r;
                r = s % 10;
                if(r==0)
                    { 
                        len++;
                    }
                else break;
                t++;
                s /= 10;
            }
           
            return len;
        }

发现这样的方法还是错误，发现是存放阶乘结果的s长度不够。于是修改为long long int 定义s。结果还是失败，于是开始反思算法。

#### 修改版算法 ####

**可以将每个数拆分成其素因子的乘积，可以发现，0是由2\*5产生的，而5的数量一定小于2的数量，因此5的个数决定了结尾0的个数。  
只要计算n的阶乘中，5这个素因子出现多少次即可。**

class Solution { 
    public:
        // param n : description of n
        // return: description of return 
        long long trailingZeros(long long n) { 
            long long sum = 0;
            while (n != 0) { 
                sum += n / 5;
                n /= 5;
            }
            return sum;
        }
    };

或者是：

class Solution { 
    public:
        /* * @param n: A long integer * @return: An integer, denote the number of trailing zeros in n! */
        long long trailingZeros(long long n) { 
            // write your code here, try to do it without arithmetic operators.
            long long numFactor5 = 0;
            
            while (n >= 5)
            { 
                n = n / 5;
                numFactor5 += n;
            }
    
            return numFactor5;
        }
    };

## python解法 ##

class Solution:
        # @param n a integer
        # @return ans a integer
        def trailingZeros(self, n):
            sum = 0
            while n != 0:
                n /= 5#这里可以替换为n //= 5(//代表抹除小数部分取整数)
                sum+= n
            return sum

说实话，这种方法不太会。