Factorial Trailing Zeroes

LeetCode Q 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.

Solution

Algorithm
The number of tailing zeroes is related to the number of divisors 2 and 5. And 2 is smaller than 5, so this number is determined by the number of divisor 5.
Therefore, we calculate the number in 1 ~ n, which is multiplication of 5, 25, 125, 625,…

Code: Method 1 (Not Correct)

public int trailingZeroes(int n) {
  int num = 5, res = 0;
  while (num <= n) {
    res += n / num;
    num \*= 5;  // this will cause integer overflow 
  }
  return res;
}

Code: Method 2

public int trailingZeroes(int n) {
  int res = 0;
  while (n != 0) {
    res += n / 5;
    n /= 5;
  }
  return res;
}