问题描述
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;
}
}