leetcode [#172]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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

Note:
Your solution should be in logarithmic time complexity.

---

解决方案

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

---

注意事项

1. 并不是单纯考察求解某个数的阶乘值，因此没有必要按照给定的n先求出n!是多少，这样的话复杂度也符合o(lgn)的要求。
2. n!值末尾有0，那么必然是2和5相乘得来的（不可能是0本身）。因此，n!末尾有几个0，取决于2的个数和5的个数的最小值。可以得到的结论是，由于2比5小，因此对于任意正整数来说，阶乘各项中5的个数一定小于等于2的个数。因此，问题转化为对于给定n，从1到n相乘一共可以分解出多少个5。那么，在n大于0的条件下，不断将n除以5，将所得商累加起来，就是5的个数。