1.14 Factorial Trailing Zeros

Description

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

Note: Your solution should be in logarithmic time complexity.

Method

when we want to know the number of trailing zeros, we just need to think about how many numbers of five's multiple, since it can offer at least one trailing zero. And then in these numbers, some are special ,because they can offer more than one trailing zeros, such as 25, 50, 75, 100, so we only need to calculate the total number of multiple of 5

Time and Space Complexity

log5 n

Code

public class Solution {

public int trailingZeroes(int n) {
      int total = 0;
      while (n >= 5){
          total += n / 5;
          n = n / 5;
      }

      return total;
}

}