力扣面试150 阶乘后的零 数论 找规律 质因数

Problem: 172. 阶乘后的零

思路

👨‍🏫 大佬神解

• 一个数末尾有多少个 0 ，取决于这个数 有多少个因子 10
• 而 10 可以分解出质因子 2 和 5
• 而在阶乘种，2 的倍数会比 5 的倍数多，换而言之，每一个 5 都会找到一个 2 与之相配对成 10
  • 2 的倍数 2 4 6 8 10 …
  • 5 的倍数 5 10 …

复杂度

时间复杂度: $O(lo{g}_{5}n)$

空间复杂度: $O(1)$

Code

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