Problem: 172. 阶乘后的零
思路
👨🏫 大佬神解
- 一个数末尾有多少个
0
,取决于这个数 有多少个因子10
- 而
10
可以分解出质因子2
和5
- 而在阶乘种,
2
的倍数会比5
的倍数多,换而言之,每一个5
都会找到一个2
与之相配对成10
2
的倍数 2 4 6 8 10 …5
的倍数 5 10 …
复杂度
时间复杂度: O ( l o g 5 n ) O(log_5n) O(log5n)
空间复杂度: O ( 1 ) O(1) O(1)
Code
class Solution {public int trailingZeroes(int n) {int cnt = 0;while(n > 0){cnt += n/5;n = n/5;}return cnt;}
}