[LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数

2021年09月15日 阅读数:1
这篇文章主要向大家介绍[LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given an integer n, return the number of trailing zeroes in n!.html

Example 1:java

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:python

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.post

给一个整数n,返回n的阶乘末尾0的个数。url

找乘数中10的个数,而10可分解为2和5,而2的数量远大于5的数量,因此找出5的个数。htm

解法1:迭代Iterativeblog

解法2: 递归Recursive递归

Java:get

public class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        while (n > 0) {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
}  

Java:it

public class Solution {
    public int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
}

Python:

class Solution:
    # @return an integer
    def trailingZeroes(self, n):
        result = 0
        while n > 0:
            result += n / 5
            n /= 5
        return result  

Python:

class Solution(object):
    def trailingZeroes(self, n):
        """
        :type n: int
        :rtype: int
        """
        return 0 if n == 0 else n / 5 + self.trailingZeroes(n / 5)     

C++:

class Solution {
public:
    int trailingZeroes(int n) {
        int res = 0;
        while (n) {
            res += n / 5;
            n /= 5;
        }
        return res;
    }
};

C++:

class Solution {
public:
    int trailingZeroes(int n) {
        return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
    }
};

  

 

  

All LeetCode Questions List 题目汇总