172. Factorial Trailing Zeroes

Description

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

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

Constraints

• 1 <= n <= 104

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int trailingZeroes(int n) {
        if(n <= 0) return 0;
        
        int count = 0;
        for(int i = 5; n/i >= 1; i *= 5) {
            count += n/i;
        }
        
        return count;
    }
}

Follow up