DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 77: Python Trailing Zeros in Factorial – Genius Number Theory Trick to Count Zeros in n! Without Computing the Huge Number

#challenge #python #algorithms #programming

Welcome to Day 77 of the #80DaysOfChallenges journey! This intermediate challenge solves the classic trailing zeros in n! problem (LeetCode #172) using pure number theory: count factors of 5 in n! since 10 = 2×5 and 5s are the limiting factor. The solution iteratively divides by increasing powers of 5 in O(log n) time, avoiding computing the massive factorial itself. It's a mind-blowing insight that scales to huge n like 10^12 without overflow.

If you're into math tricks, preparing for interviews with factorial/counting questions, or dealing with large numbers in combinatorics, this "Python trailing zeros factorial" script is elegant, optimal, and the exact method used in competitive programming.

Example:

25! has 6 trailing zeros (from 5,10,15,20,25×2)

💡 Key Takeaways from Day 77: Trailing Zeros Function

This task features a function that accumulates floor(n/5) + floor(n/25) + floor(n/125) + ... for powers of 5. It's a divide-by-powers pattern: count contributions from higher multiples. We'll detail: function with while and divisor multiply, loop for power accumulation, and main with input.

1. Function Design: Simple Init and While

The trailing_zeros function takes n, returns count:

def trailing_zeros(n: int) -> int:
    """Return the number of trailing zeros in n!."""
    count = 0
    divisor = 5

    while divisor <= n:
        count += n // divisor        # count multiples of current power of 5
        divisor *= 5                 # move to next power of 5

    return count
Enter fullscreen mode Exit fullscreen mode

Count starts 0, divisor 5. While <=n, add floor(n/divisor), multiply divisor by 5. For n=25: 25//5=5, 25//25=1, total 6.

2. Loop Processing: Power Accumulation 

    while divisor <= n:
        count += n // divisor
        divisor *= 5
Enter fullscreen mode Exit fullscreen mode

Each iteration counts extra 5s from higher powers (25=5×5, 125=5×5×5). Stops when divisor > n. O(log_5 n) iterations, ultra-fast.

3. Main Interactive: Input and Print

Script prompts n, calls, prints:

n = int(input("Enter a non-negative integer: ").strip())
zeros = trailing_zeros(n)

print(f"Trailing zeros in {n}! : {zeros}")
Enter fullscreen mode Exit fullscreen mode

Assumes non-negative, prints zeros. Try 100 → 24.

🎯 Summary and Reflections

This trailing zeros uses number theory to avoid bigints. It reinforced:

  • 5s limit 10s: 2s always more than 5s.
  • Power multiply: divisor*=5 for next level.
  • Floor div: n//divisor counts contributions.

Reflections: For primes other than 5, same pattern. Mind-blowing efficiency.

Advanced Alternatives: Recursive count(n//5) + n//5. Math formula but loop clearer. Your factorial trick? Share!

🚀 Next Steps and Resources

Day 77 counted zeros mathematically. In #80DaysOfChallenges? Huge n? Post!

Top comments (0)