172. Factorial Trailing Zeroes

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

Follow up: Could you write a solution that works in logarithmic time complexity?

 

Example 1:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: n = 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Example 3:

Input: n = 0
Output: 0

 

Constraints:

  • 0 <= n <= 104

Rust Solution

struct Solution;

impl Solution {
    fn trailing_zeroes(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            sum += n / 5;
            n /= 5;
        }
        sum
    }
}

#[test]
fn test() {
    assert_eq!(Solution::trailing_zeroes(3), 0);
    assert_eq!(Solution::trailing_zeroes(5), 1);
    assert_eq!(Solution::trailing_zeroes(10), 2);
}

Having problems with this solution? Click here to submit an issue on github.