Problem 172

Factorial Trailing Zeros

Posted by Ruizhi Ma on July 5, 2019

问题描述

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

Example 1:

Input: 3

Output: 0

Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5

Output: 1

Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

解决思路

一开始用递归算阶乘,然后for循环统计末尾0,但超时了。后来看了一下,发现有规律:所有末尾有0的数,例如xxxx0000,一定可以写成xxxxx * (2^k * 5^k)的形式, 而很容易可以知道,分解因式时,2的个数远大于5的个数,所以,这个题就转变成,n!分解质因数后,有几个5

问题解惑

有些数,比如25!,里面会有多个5,所以循环除5,就是处理遇到5倍数的时候,出现多个5的情况

代码

package leetcode;

public class FactorialTrailingZeroes {
    public int trailingZeroes(int n) {
        int res = 0;

        while(n != 0){
            res += n / 5;
            n /= 5;
        }

        return res;
    }
}


0 comments
Anonymous
Error: Bad credentials.
Markdown is supported

Be the first person to leave a comment!