35
\$\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.

Submissions

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

# Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

# Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

# Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the leaderboard snippet:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 79762; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43444; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    if (/<a/.test(lang)) lang = jQuery(lang).text();
    
    languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang > b.lang) return 1;
    if (a.lang < b.lang) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<div id="language-list">
  <h2>Winners by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – xnor May 12 '16 at 2:39
  • \$\begingroup\$ Can we assume that n! will fit within our languages' native integer type? \$\endgroup\$ – Alex A. May 12 '16 at 2:45
  • \$\begingroup\$ @AlexA. Yes you can. \$\endgroup\$ – Arcturus May 12 '16 at 3:01
  • \$\begingroup\$ Can n be an input string? \$\endgroup\$ – Conor O'Brien May 12 '16 at 3:10
  • 15
    \$\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 '16 at 10:45

52 Answers 52

1
2
1
\$\begingroup\$

Pyt, 5 bytes

5←!ḋɔ

Explanation:

5             Pushes 5
 ←            Gets input
  !           Factorial
   ḋ          Prime factors (with duplicates)
    ɔ         Count occurrences of 5 in the list of prime factors

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

J, 15 bytes

+/<.(%5:^>:@i.)

Who needs to calculate factorial?

Probably longer than with though :p

Explanation when I get home

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ (%5:^>:@i.) -> (%5^1+i.) \$\endgroup\$ – FrownyFrog Jan 4 '18 at 3:06
1
\$\begingroup\$

Runic Enchantments, 21 bytes

Rl1)?@+
/:>i5,'fA:0)?

Try it online!

Uses the same f(n) = n/5 + f(n/5) as other answers. Just took some coercion to to reduce the footprint as much as possible. Fortunately > does nothing when executed (it simply marks the entry point) and i pushes nothing to the stack when no more input remains.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Python 2, 33 bytes

f=lambda n:n/5+f(n/5)if n>0else 0

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Wow, I had no idea Python could parse out the >0 like that. \$\endgroup\$ – Calculuswhiz Aug 17 at 19:37
0
\$\begingroup\$

CJam, 9 bytes

l~m!mf5e=

Try it online!

Just counting the 5's 5e= in the prime factorization mf of the factorial m! of the input l~.

Doesn't work for big factorials, since they don't fit into an integer.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

C, 53 bytes

 i,r;z(n){for(;i=n--;)for(;i=i%5?0:i/5;)r++;return r;}

Counting 5s in the sequence that makes up the factorial, instead of calculating the factorial and then counting its 5s.

Full program:

i,r;z(n){for(;i=n--;)for(;i=i%5?0:i/5;)r++;return r;}
#include <stdio.h>
int main(int argc, char **argv) {
    int n;
    sscanf(argv[1], "%d", &n);
    printf("%d -> %d\n", n, z(n));
    return 0;
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Convex, 6 bytes

¡mf5e=

Use Java interpreter or this alternate version that works on TIO: Try it online

This would be 4 bytes if I was finished getting rid of 2 char operators....

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PowerShell v2+, 60 bytes (but see the NB below)

A completely different approach, doing exactly what is requested by the challenge. ;-)

$a=2..$args[0]-join'*'|iex;"$a".length-"$a".Trim('0').length

Takes input $args and creates a dynamic range .., then -joins it together with * for multiplication, pipes that to iex (similar to eval) to compute the factorial. Store that in $a.

We then take the length of the string representation and subtract off the length of the string representation after we've passed it to .Trim('0') which will remove leading and trailing zeroes. Since there will never be leading zeroes, this gets us the result we want.

NB: The above will work for up to n=17 without a problem, as even though 17! is bigger than [Int]::MaxValue, since we didn't explicitly specify the casting for $a, PowerShell will dynamically convert it to [double] for us upon overflow. Yeah ... in PowerShell, [int] will overflow to [double] if not explicitly cast. No, I don't know why it goes to that rather than [int64].

However, at 18!, PowerShell will automatically convert the number to scientific notation when the implicit .ToString() is called (i.e., when encapsulating it within quotes), in order to preserve significant digits. We can get around that with explicit formatting instead -- $a="{0:0}"-f(2..$args[0]-join'*'|iex);$a.length-$a.Trim('0').length -- at 67 bytes. That will get us up to 20! before we start to run into loss of precision.

Thus, to handle an "arbitrary" input, we'll need to combine the above explicit formatting with the [bigint] datatype ...

PowerShell v2+, 80 bytes

$a="{0:0}"-f("[bigint]"+(2..$args[0]-join'*')|iex);$a.length-$a.Trim('0').length

This will prepend an explicit cast of [bigint] to the first number in the range 2, and in PowerShell the datatype on the left of the operator is used for output, so that [bigint] datatype will continue through the rest of the factorial calculation.


An few examples of the three methods at some key points, with some additional output text showing what's happening in the background -- the first output is the top code, the middle is with the explicit string formatting, and the bottom is with the [bigint] datatype.

PS C:\Tools\Scripts> .\golfing\zeroes-at-end-of-factorial.ps1 17
(Normal) 355687428096000 = 3
(Format) 355687428096000 = 3
(BigInt) 355687428096000 = 3

PS C:\Tools\Scripts> .\golfing\zeroes-at-end-of-factorial.ps1 18
(Normal) 6.402373705728E+15 = 0
(Format) 6402373705728000 = 3
(BigInt) 6402373705728000 = 3

PS C:\Tools\Scripts> .\golfing\zeroes-at-end-of-factorial.ps1 21
(Normal) 5.10909421717094E+19 = 0
(Format) 51090942171709400000 = 5
(BigInt) 51090942171709440000 = 4

PS C:\Tools\Scripts> .\golfing\zeroes-at-end-of-factorial.ps1 100
(Normal) 9.33262154439441E+157 = 0
(Format) 933262154439441000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000 = 143
(BigInt) 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000
00000000 = 24

PS C:\Tools\Scripts> .\golfing\zeroes-at-end-of-factorial.ps1 666
(Normal) Infinity = 0
(Format) Infinity = 0
(BigInt) 101063205684078149339082270812987645175758239832414541134042080735741380210369702298920280680149101204098980220355752703933970405713072930283454242384
016585642874066153029797241068282869939717688434251350949378748077490349338925526287834176188326189942648494465716169313138031111761957305152642332038964180541
081606760789306748325981681536460982866866274811038560365797328460484207809414155642770874534510059882948847250594907196772727091196506088520929434066550648022
642608335790150309778114083249701373807911277761571911620331754219999948922714475266708579675248268885046126373228453917614236582397369676453760327876932228670
885547506983568164371084614056976933006577541441308350104365957229945444651724282400214055514046429629100190143841467573055296491456926973403850076414055114364
283612861330473414734808609512385966092678846067118146921625221337465049955783174195059482714722569989641408869425126104519667256749553222882671938160611697400
311264211156133257350321296072971178199390387741639438171846476552757501425212904028323696392262434445697502405816736843180906854457725847298397943781807264821
360865009874936976105696120379126536366566469680224519996204004154443821032721047698220334845859609307929656956126740947391412413210205581149373619966878853487
232170536051130524871079644147921335454258357607659625021345466796883799602327316306909470042946710666392541958119313633986054565867362395523193239940480940410
876723200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000 = 165
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

dc, 26

?[5/dd0<m]dsmx[+z1<m]dsmxp
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

rs, 95 bytes

(\d+)/(_)^^(\1)
_(_+)/_\1 \1
+_(_+) _(_+)$/(_\1)^^((^^_\2)) \2
 _$/
(_+)/(^^\1)
.*?(0*)$/(^^\1)

Live demo.

Note that I can't test this with large inputs such as 100. Feel free to try it, but you'd need over 8.486e145 TB of RAM...

An explanation of the first 5 lines is available here. The last line just counts the zeroes at the end.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Haskell, 39 bytes

Can't compete with @xnor, but it was fun and the result is a different approach:

f n=sum$[1..n]>>= \i->1<$[5^i,2*5^i..n]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

CJam, 11

Efficient solution, similar to other answers.

Loop version:

ri{5/_}h]:+

Try it online

Explanation:

ri      read the input and convert to integer
{…}h    do…while
  5/    divide by 5
  _     duplicate the last number
         the loop terminates when the number reaches 0
]:+     add all the numbers from the stack

Recursive version:

ri0{5/_j+}j

Try it online

Explanation:

ri       read the input and convert to integer
0{…}j    calculate with memoized recursion and initial value 0 for input 0
  5/     divide by 5
  _      duplicate the result
  j      calculate the number of zeros recursively for that number
  +      add the 2 results
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PHP, 62 bytes

for($n=$z=0;++$n<=log(125,5);){$z+=floor(125/(5**$n));}echo$z;
exploded view
for ($n=$z=0; ++$n<=log(125,5); ) {
  $z += floor( 125 / (5 ** $n) );
}
echo $z;

The starting point for many of the answers here is that every 5th factor adds a single 0, since there are 2-3 even numbers that precede it, and you can only get a new 0 with both a factor of 2 and a factor of 5.

If we assumed this to be true, the answer is simple in PHP, in 23 bytes:

echo(floor(argv[0]/5));

However, consider 25!. 24! has 4 0's in it (because of 5, 10, 15, and 20). But 25 adds two 5's to the equation, meaning 25! has 6 0's in it. So we have to account for 5^n as well.

| improve this answer | |
\$\endgroup\$
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. Luckily, we don't need to deal with n==0 (would the solitary zero count as 'trailing'?)

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Erlang, 33 bytes

f(0)->0;f(N)->N div 5+f(N div 5).

Same tactic as in xnor and Cᴏɴᴏʀ O'Bʀɪᴇɴ's answers.

Ungolfed:

f(0) -> 0;
f(N) when N > 0 -> N div 5 + f(N div 5).
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

bc, 51 bytes

define f(x){if(x){return x/5+f(x/5)}else{return 0}}

Same tactic as in xnor and Cᴏɴᴏʀ O'Bʀɪᴇɴ's answers, but longer.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

GML, 35 bytes

a=argument0 while a/=5b+=a return b
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Japt, 6 bytes

Can only handle inputs up to 21 due to JavaScript's integer limitations.

Êk xv5

Try it


Explanation

Ê          :Factorial
 k         :Prime factors
   v5      :Divisible by 5?
  x        :Reduce by addition
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

PHP, 43 39 bytes

based on Toby Speight´s C solution

function f($n){return$n?f($n/=5)+$n|0:0;}

Try it online.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Stax, 4 bytes

╩+Pî

Run and debug it

I omitted the final test case. The algorithm is correct, but the time requirements are beyond my patience or predicted lifespan.

Method:

  1. Compute factorial
  2. Calculate "multiplicity" by 10.
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Forth (gforth), 38 bytes

Based on Toby Speight's C Solution

: f dup 0> if 5 / dup recurse + then ;

Try it online!

Code Explanation

: f           \ start a new word definition
  dup 0> if   \ check if n > 0
    5 / dup   \ divide by 5 and duplicate if so
    recurse   \ call f on n/5
    +         \ add to sum
  then        \ end if
;             \ end word definition
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Keg, -rR, 9 bytes

0&¡÷{0=|⑹

Try it online!

I'm sure there is a more efficient way by using some sort of formula, but a counting method was the best I could think of.

Explained

0&¡÷{0=|⑹
0&          #Store 0 in the register
  ¡÷        #Take the factorial of the (implicit) input and item split
    {0=     #While the top item is still 0:
       |⑹  #    Increment the register
            #-rR prints the register as an integer at end of execution
| improve this answer | |
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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