39
\$\begingroup\$

Write a program or function that finds the number of zeroes at the end of n! in base 10, where n is an input number (in any desired format).

It can be assumed that n is a positive integer, meaning that n! is also an integer. There are no zeroes after a decimal point in n!. Also, it can be assumed that your programming language can handle the value of n and n!.


Test cases

1
==> 0

5
==> 1

100
==> 24

666
==> 165

2016
==> 502

1234567891011121314151617181920
==> 308641972752780328537904295461

This is code golf. Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
10
  • \$\begingroup\$ Related. \$\endgroup\$
    – xnor
    May 12, 2016 at 2:39
  • 1
    \$\begingroup\$ Can we assume that n! will fit within our languages' native integer type? \$\endgroup\$
    – Alex A.
    May 12, 2016 at 2:45
  • 1
    \$\begingroup\$ @AlexA. Yes you can. \$\endgroup\$
    – Arcturus
    May 12, 2016 at 3:01
  • 17
    \$\begingroup\$ I think this would be a better question if you were not allowed to assume n! would fit into your integer type! Well, maybe another time. \$\endgroup\$
    – A Simmons
    May 12, 2016 at 10:45
  • 1
    \$\begingroup\$ @ASimmons Most of the answers so far, or at least the ones that use the floor division trick, don't rely on that assumption anyway. \$\endgroup\$
    – Alex A.
    May 12, 2016 at 16:53

62 Answers 62

1 2
3
0
\$\begingroup\$

GNU coreutils, 34 bytes

seq $1|factor|tr \  \\n|grep -cx 5

The set of prime factors of the factorial n! is the union of the sets of prime factors of 1..n. We just need to count the number of fives, as this will always be less than the number of twos, and it takes one five and one two to produce each trailing zero. Happily, n==0 correctly produces 0, even though the question doesn't require that.

The output of factor is not quite what we want (in fact, in every golf I do, the reprinting of input is a nuisance):

$ seq 6|factor
1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3

By replacing each space with a newline, we can match lines that are exactly 5 (this handily eliminates the 5: prefix for that line), and count the total.

You will probably run out of memory and/or time trying the last of the example inputs, but there's nothing in the program itself that wouldn't work.

\$\endgroup\$
0
\$\begingroup\$

Risky, 6 bytes

!!?+_0__/\\?

Try it online!

Explanation

! length
!       factorial
?         input
+     +
_
0         0
_   apply function
_
/         5
\     find indices in
\       prime factors
?         argument
\$\endgroup\$
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.