Factorial Trailing Zeroes
Maintained by Vikas D, software engineer
The factorial n! is the product of every integer from 1 up to n, so it grows enormously fast. Even for moderate n the value is far too large to hold in a normal integer type, so any approach that builds the factorial and inspects its digits is doomed on the larger inputs.
A trailing zero appears only when the product picks up a factor of 10. Every 10 is the result of one factor of 2 multiplied by one factor of 5, so the count of trailing zeroes equals the number of complete (2, 5) pairs hidden inside the product.
Inside a factorial the even numbers supply factors of 2 far more often than any number supplies a factor of 5. Twos are never the bottleneck, so the answer is simply the total number of times 5 divides into n!.
Return that total count of 5s. Note that some numbers contribute more than one five: 25 is 5 times 5, 125 is 5 times 5 times 5, and so on, so those higher powers must be counted again.
Examples
5! = 120, which ends in a single zero. Among 1 through 5 only the number 5 carries a factor of 5, so there is exactly one 5 and one trailing zero.
The multiples 5, 10, 15, 20, 25 each give at least one 5 (five of them), and 25 = 5 times 5 gives an extra one, for a total of six factors of 5.
3! = 6 has no factor of 5 anywhere, so there are no trailing zeroes.
Constraints
- 0 <= n <= 10^4
- Return the count as a plain integer.
- n = 0 is valid and 0! = 1, which has zero trailing zeroes.
Visible test cases
- trailingZeroes(0) == 0
- trailingZeroes(3) == 0
- trailingZeroes(5) == 1
- trailingZeroes(10) == 2
- trailingZeroes(25) == 6
- trailingZeroes(100) == 24
Hints
Hint 1
You cannot compute n! directly for large n, so look for a property of the digits instead of the digits themselves.
Hint 2
A trailing zero comes from a factor of 10, and 10 = 2 times 5. Which of those two prime factors is the scarce one inside a factorial?
Hint 3
Count factors of 5: add floor(n/5), then floor(n/25), then floor(n/125), and keep going while the power of 5 is at most n.
Approaches
Build the factorial and strip zeroes
Time O(n) multiplications, but each multiplication is on a number with O(n log n) digits, so it is slow and memory heavy · Space O(n log n) to store the giant factorialMultiply 1 through n into a big integer, then peel off trailing zeroes by repeatedly checking divisibility by 10.
- Compute the product of all integers from 1 to n.
- While the product is divisible by 10, divide by 10 and increment a counter.
- Return the counter.
Count factors of 5 directly
Time O(log_5 n) because the power of 5 grows geometrically · Space O(1)The number of trailing zeroes equals the number of times 5 divides n!, because factors of 2 are always at least as plentiful. Sum floor(n / 5^k) over increasing powers of 5.
- Start a running count at 0 and a power variable at 5.
- While the power is at most n, add floor(n / power) to the count.
- Multiply the power by 5 and repeat, which captures the extra 5s contributed by 25, 125, and beyond.
- Return the count.
Common mistakes
- Counting only floor(n/5) and stopping. Numbers like 25, 125, and 625 contribute additional factors of 5 that you must add via the higher powers.
- Trying to compute n! in a fixed-width integer type; it overflows almost immediately and gives wrong answers for n beyond about 20.
- Letting the loop power overflow or never terminate. Compare power against n before each step, and grow power by multiplying so it climbs fast.
- Mishandling n = 0 (and n less than 5): the loop body never runs and the answer should correctly be 0.
Follow-up variations
- Given a target number of trailing zeroes z, find the smallest n such that n! ends in exactly z zeroes, or report that none exists.
- Count trailing zeroes of n! in a different base, for example base 12, where you must track the limiting prime power rather than just fives.
- Return the last non-zero digit of n! instead of how many zeroes precede it.