We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Factorial Trailing Zeroes

Number: 172

Difficulty: Medium

Paid? No

Companies: Microsoft, Meta, Google, Bloomberg

Problem Description

Given an integer n, return the number of trailing zeroes in n! (n factorial). The trailing zeroes are caused by the factors 10, which come from multiplying 2 and 5. Since there are more factors of 2 than 5 in n!, the number of trailing zeroes is determined by the number of times 5 is a factor in the numbers from 1 to n.

Key Insights

  • Trailing zeroes are produced by factors of 10 (2 * 5) in the factorial.
  • There are more 2s than 5s in n! so counting the number of 5 factors will suffice.
  • Count how many multiples of 5, 25, 125, etc., since each contributes additional factors of 5.
  • This approach runs in logarithmic time relative to n.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

We count the factors of 5 in n! by repeatedly dividing n by 5. The intuition is that every 5th number contributes at least one factor of 5, every 25th contributes an extra factor because 25 = 5*5, and so on. We continue this division until n becomes 0. This avoids computing the factorial directly, providing a very efficient solution. The algorithm uses a simple loop and integer division, resulting in logarithmic time complexity and constant space usage.

Code Solutions

# Python solution to count trailing zeroes in n!

def trailingZeroes(n):
    # Initialize count of trailing zeroes
    count = 0
    # Loop until n becomes zero
    while n > 0:
        # Divide n by 5 to count multiples of 5
        n //= 5
        # Add the result to the overall count
        count += n
    # Return the total count of trailing zeroes
    return count

# Example usage:
print(trailingZeroes(5))  # Expected output: 1
← Back to All Questions