Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/172.html
172 Factorial Trailing Zeroes
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.
@tag-math
Algorithm
To find the number of 10 in the multiplier, and 10 can be decomposed into 2 and 5, and the number of 2 is much greater than the number of 5 (for example, there are 2 5
s in 1 to 10, 5 2
s), then this question is find the counts of 5
.
One thing that still needs to be noted is that numbers like 25, 125, which contain more than a 5, need to be taken into consideration.
Code
-
public class Factorial_Trailing_Zeroes { public static void main(String[] args) { Factorial_Trailing_Zeroes out = new Factorial_Trailing_Zeroes(); Solution_iteration s = out.new Solution_iteration(); s.trailingZeroes(126); // System.out.println(s.trailingZeroes(126)); } public class Solution_iteration { public int trailingZeroes(int n) { int res = 0; while (n > 0) { res += n / 5; n /= 5; /* System.out.println(res); 25 30 31 31 */ } return res; } } class Solution { public int trailingZeroes(int n) { return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); } } } ############ class Solution { public int trailingZeroes(int n) { int ans = 0; while (n > 0) { n /= 5; ans += n; } return ans; } }
-
class Solution: def trailingZeroes(self, n: int) -> int: ans = 0 while n: n //= 5 ans += n return ans ############ class Solution(object): def trailingZeroes(self, n): """ :type n: int :rtype: int """ count, k = 0, 5 while n: k = n / 5 count += k n = k return count
-
class Solution { public: int trailingZeroes(int n) { int ans = 0; for (int i = 5; i <= n; i *= 5) ans += n / i; return ans; } };
-
func trailingZeroes(n int) int { ans := 0 for n > 0 { n /= 5 ans += n } return ans }
-
function trailingZeroes(n: number): number { let ans = 0; while (n > 0) { n = Math.floor(n / 5); ans += n; } return ans; }