Count Trailing Zeros in Factorial of a Number

Problem: Given a number n, find the number of trailing zeros in n! (n factorial), without computing the factorial directly.

Constraints: n can be large (up to 10^9), making direct factorial computation infeasible.

Example: Input: n=10 -> 10! = 3628800 -> Output: 2

Approach: Trailing zeros come from factors of 10 = 2*5 in n!; since factors of 2 vastly outnumber factors of 5 in any factorial, the count of trailing zeros equals the count of factor 5s in n!. Compute this as floor(n/5) + floor(n/25) + floor(n/125) + ... until the term is 0, summing contributions from 5, 25, 125, etc. Runs in O(log_5 n).