Given an integer 1 ≤ N ≤ 1,000,000 as input, output the last non-zero digit of N!, where ! is the factorial (the product of all numbers from 1 to N, inclusive). This is OEIS sequence A008904.

Your program needs finish within 10 seconds on a reasonable machine for any valid input.

Test Cases

1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4

This is a so the shortest code in bytes wins!

  • Single function or complete program? – Joey Feb 8 '11 at 12:15
  • @joey No, they are just test cases. Single Input, Single Output. – fR0DDY Feb 8 '11 at 14:09
  • @joey Complete program. – fR0DDY Feb 8 '11 at 14:36
  • 1
    Requirement for a full program is discouraged... – Erik the Outgolfer Jan 18 at 16:12
  • 2
    @EriktheOutgolfer this is from ~7 years ago, so I don't think that was determined at the time – NoOneIsHere Jan 18 at 22:35

27 Answers 27

up vote 8 down vote accepted

Ruby - 63 chars

f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}

Source - http://oeis.org/A008904

Handles f upto a thousand digits under a second.

Test

irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4

Mathematica, 45 36 bytes

Last@Select[IntegerDigits[#!],#>0&]&

Very readable for a winning answer. :) (Then again, there's no GolfScript & Co. submission yet.)

This handles input 1,000,000 in about 5 seconds on my machine.

  • Mathematica is pretty much the perfect language for this question. – Michael Stern Feb 2 '15 at 0:03

Python - 75

n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10

05AB1E, 4 bytes

!0м¤

Try it online!

Explanation

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display
  • The TIO version timed out (60s) on the last test case - how did you get it within 10s on a "reasonable machine"? – Toby Speight Feb 20 at 14:38

PARI/GP - 27 bytes

This trades speed for size -- the testcase takes a long time (~6 seconds).

n->n!/10^valuation(n!,5)%10

This version is much faster (~15 microseconds) but takes 81 bytes:

n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)

You can use this (non-golfed) code to test either:

[%(10^n) | n <- [1..6]]

Windows PowerShell, 53 56 59 60 63 73 90

($a=1).."$input"|%{$a="$($a*$_)".trim('0')%1e7}
$a%10

Notes:

  • Takes longer than a minute for a number close to 100,000. However, removing zeroes at the end requires a convert to string, doing calculations requires a number, so the conversions are inevitable in any case.

History:

  • 2011-02-08 10:31 (90) – First attempt.
  • 2011-02-08 10:33 (73) – Modulus is shorter than slicing and joining.
  • 2011-02-08 10:34 (63) – Unnecessary trim.
  • 2011-02-08 10:37 (60) – Unnecessary cast to a number. Modulus does that just fine, already.
  • 2011-02-08 10:40 (59) – Some inlining.
  • 2011-02-08 11:00 (56) – What did I say before about modulus being shorter? Applies to the output as well.
  • 2011-02-08 11:01 (53) – Casting $input to a string is enough; the cast to int is applied implicitly.

Perl, 53 58 61 characters

All whitespace can be removed, but I left it in for "readability". Note: not using some silly explicit formula from Sloane.

sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}

Calculates f(10^6) in 8.7 seconds on my machine.

Update: OP wanted it to be a whole program:

$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10

That makes it 55 characters.

CJam - 28

1ri{I)*_AbW%{}#A\#/1e7%}fIA%

You can try it at http://cjam.aditsu.net/ for values up to 10000 or so; for larger numbers you should use the java interpreter. 1000000 runs in about 3 seconds on my laptop.

Explanation:

Unfortunately the straightforward solution is too slow, so I'm keeping only the last 7 digits (before the trailing zeros) after each multiplication.

1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit

Note: this language is a lot newer than the question.

Mathematica, 34 bytes

Mod[#!/10^IntegerExponent[#!],10]&

Jelly, 4 bytes

!Ṛȯ/

Try it online!

Explanation

Uses the fact that when (reverse a list; does not vectorize) is applied to an integer it automatically takes D (digits) first.

With input 8:

!Ṛȯ/
!     Factorial: 8! = 40320
 Ṛ    Reverse: [0,2,3,0,4]
   /  Reduce by...
  ȯ   ...logical OR: ((((0ȯ2)ȯ3)ȯ0)ȯ4) = first truthy element = 2

I don't think there is a one-byte "first truthy element" (which ȯ/ acts as) but if there is then this can be shortened to three bytes total.

Java (OpenJDK 8), 62 bytes

n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}

Try it online!

Similar to @Kevin Cruijssen but saves 5 bytes by combining the loops.

  • Welcome to PPCG! Nice first post! Hope you stick around! – Riker Jan 19 at 1:11
  • Welcome to PPCG! I agree with @Riker, great first post. Well done golfing my code by combining the loops. You can golf 1 more byte in your current answer by replacing || with |, and an additional byte by replacing ==0 with <1. Enjoy your stay! – Kevin Cruijssen Feb 1 at 12:19

PHP - 105

 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}

Runs under 10 seconds with the given testcase.

Python3

239 Chars

Can do 10000 in ~3.2 seconds (Ideone cuts me off at 8 seconds, i'm sure it'll take longer than 10secs though :( )

from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)

Python2.6

299 Chars (a bit faster)

from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)

Haskell, 78 characters

f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)

(Would probably need to be compiled to compute 1,000,000! in 10 secs).

J – 42 40 characters

A whole program. Save this program in a file and run with jconsole script.ijs 1234. Notice that this program does not exit the interpreter after printing a result. Type ^D or exit]0 to exit the interpreter.

echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV

Here is an explanation:

  • x #. y interprets the integer vector y as a base x number; for example, 10 #. 1 2 3 4 yields 1234.
  • u inv yields the inverse of a verb u. In particular, x #. inv y represents y as a base x number; for example, 10 #. 1234 yields 1 2 3 4. Notice that inv is defined as ^:_1, that is, u applied -1 time.
  • x * y is the product of x and y, thus x 10&#.inv@* y yields a base-10 representation of the product of x and y.
  • x # y copies the n-th item of y as often as the n-th item of x; when x is a vector of booleans, x selects which items of y to take. For instance, 1 0 1 0 # 1 2 3 4 yields 1 3.
  • * y yields the signum of y.
  • x u~ y is the reflexive of u, that is, the same as y u x.
  • Thus, y #~ * y yields a vector of all items of y that are positive. In tacit notation, this can written with a hook as (#~ *).
  • {: y yields the last item in y.
  • assembled together, we get the tacit phrase ([:{:@(#~*)10&#.inv@*).
  • u/ y is the reduction of y, that is, the dyadic verb u inserted between elements of y. For instance, +/1 2 3 4 is like 1 + 2 + 3 + 4 and yields 10.
  • Thus, the phrase ([:{:@(#~*)10&#.inv@*)/ y yields the last digit of the product of the items of y.
  • ARGV is a boxed vector of the command line arguments.
  • ".>{:ARGV is the last argument unboxed and interpreted as a number.
  • i. y computes natural numbers from 0 to y - 1.
  • Thus, 1+i. y yields natural numbers from 1 to y. I could have also used >: increment here, but 1+ is clearer at the same cost of characters.
  • The entire program just applies 1+i.".>{:ARGV (the vector of 1 to the number in the last command line argument) to the verb ([:{:@(#~*)10&#.inv@*)/ and prints the result with echo.

Pyt, 5 bytes

!₫ą0⦋

Explanation:

         Implicit input (n)
!        n!
 ₫       Reverse the digits of (n!) - this disregards leading zeroes after reversal
  ą      Convert to array of digits
   0⦋    Get the first element

Try it online!

R, 63 55 51 46 bytes

Computes factorial, extracts the last non-zero digit. Thanks to Giuseppe for providing the basic structure.

(y=(gamma(scan()+1))%/%10^(0:1e5)%%10)[!!y][1]

Try it online!

Alternatively, my old 51-byte answer:

Calculates factorial, converts to character, removes all 0s, and then takes the final character. Saved 2 bytes thanks to Giuseppe.

substring(x<-gsub("0","",gamma(scan())+1),nchar(x))

Try it online!

  • 1
    gamma(x+1) is shorter than factorial(x) – Giuseppe Jan 18 at 18:44
  • without string conversion, the best I managed to get was (y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1] at 54 bytes. – Giuseppe Jan 18 at 18:49
  • @Giuseppe We can replace nchar(x) with 1e5 for a 46-byte solution! Nice going. – rturnbull Jan 18 at 21:54

><>, 25 bytes

v:a%:?n-a,!
1
>$::?!.1-}*

Try it online!

Handles 0! correctly as well. Value passed in through the -v flag.

  • Test case 1000 doesn't produce any output on TIO - what's wrong? – Toby Speight Jun 5 at 10:27

C, 150 140 135 bytes

r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}

This is the version for ASCII systems; replace the string 33436 with 11214 for an EBCDIC system, or with \1\1\2\1\4 for a portable program.

C solutions are a bit hampered by the requirement to provide a full program; however, this does answer the question fully.

Try it online (requires Javascript):

Explanation

It's based on the algorithm outlined in Least Significant Non-Zero Digit of n!, turned around so that we recurse in to find the highest power of five, and do the calculation on the way out. The tables of constants were too big, so I reduced them by finding a relationship between the previous residue r, the current digit d and the recursion depth k:

     0    1       2       3    4  =d
  0  0  3×2^k  1×2^2k  3×2^3k  2
  1  1  1×2^k  2×2^2k  1×2^3k  4
r 2  2  2×2^k  4×2^2k  2×2^3k  3
  3  3  3×2^k  3×2^2k  3×2^3k  2
  4  4  4×2^k  4×2^2k  4×2^3k  1

For r>0, this resolves to a constant times r times 2^dk (mod 5); the constants are in a[] below (inlined in the golfed code). We also observe that (2^4)%5 is 1, so we can reduce the exponent to avoid overflowing the range of int.

const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x){
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1<<d*k%4) % 5;
}

int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}

Tests:

$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4

Performance is respectable, too. Here's a maximum input for a system with 32-bit int:

$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s

I got the same timings with a maximal 64-bit int, too.

  • It may be of interest to note that 2147483647! has over 19 billion digits, and (2^63-1)! over 170,000,000,000,000,000,000 digits, so this is a big win over calculating the factorials. 1000000! as specified in the question is feasible to calculate on current hardware; that's only 5½ million digits. :-) – Toby Speight May 17 '16 at 9:49

Add++, 11 bytes

L,RB*EDBFEZ

Try it online!

Attache, 26 bytes

Last@`\&:(All@V)@Digits@`!

Try it online!

Explanation

Last@`\&:(All@V)@Digits@`!

This is a composition of 4 functions:

  • `! - this is a functional version of the factorial operator
  • Digits - this gets the digits of the factorial
  • \&:(All@V) - This is a selection function. It works by left-bonding (&:) the function All@V to \, which is select. In turn, All@V is a short way of testing if a number is not 0. It works by casting its input to a vector 0 -> [0] then querying if all those members are truthy (i.e. not 0). This gives the digits of the number without 0s.
  • Last - this simply obtains the last member of this array.
  • This seems incredibly slow - the TIO timed out (1 minute) on the 100000 test case - how did you get the 1000000 result within 10 seconds? – Toby Speight Feb 20 at 14:35
  • @TobySpeight When I answered this challenge, that particular requirement was not there (check the revision history). – Conor O'Brien Feb 20 at 14:42
  • Ah, I should have looked at the history! You did verify all the testcases in the question, though? – Toby Speight Feb 20 at 15:01
  • It seems there was a flurry of answers during the period that the time limit was removed from the question - that's unfortunate, really. – Toby Speight Feb 20 at 15:09
  • @TobySpeight Yes, I did. It is unfortunate, and I'm not sure of the policy regarding this. – Conor O'Brien Feb 20 at 16:07

APL (Dyalog Unicode), 18 15 bytes

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘!

Try it online!

Tacit prefix function. Returns the correct digit for a single test case, or a string of digits for multiple test cases.

Thanks to @Adám and @ErikTheOutgolfer for 3 bytes each.

How?

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘! ⍝ Main function. Argument is a number following the !.
              ! ⍝ Factorial
             ∘  ⍝ then
            ⍕   ⍝ Format (stringify)
        ⍎¨⍵}    ⍝ Execute (turn to number) each digit of the argument
      0≠        ⍝ Check if each is ≠0. This returns a boolean vector
     ⍨          ⍝ Swap arguments for the following fn/op
   ⍵/           ⍝ Replicate. This takes a boolean vector as left arg and returns the truthy elements of the right arg. E.g.: 1 1 0/1 2 3 → 1 2.
{⊢/             ⍝ Reduce. This returns the rightmost (last) element of a vector argument.

APL NARS, 28 bytes, 14 chars

{↑≠v/v←⌽⍎¨⍕!⍵}

I don't know why but this pass the test:

  q←{↑≠v/v←⌽⍎¨⍕!⍵}       
  q¨1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 6 4 2 2 4 2 8 8 8 6 8 2 

Perl 6,  26  35 bytes

{[*](1..$_)~~/.*<(<-[0]>/}

Try it


As a full program:

put [*](1..@*ARGS[0])~~/.*<(<-[0]>/

Try it

Expanded:

{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}

AWK, 47 57 bytes

{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1

Try it online!

Original solution did not handle "large" input values very well. Could add -M to force it to work, but that also requires a lot more processing time.

  • Yeah, @TobySpeight , inf doesn't % very well. :( – Robert Benson Feb 20 at 16:05
  • Ah... looking at the version of the question I answered, large numbers weren't required. – Robert Benson Feb 20 at 16:14

Japt, 6 bytes

Came up with a few different 6-byters but I liked this one best. I'm convinced there must be a way to do it in 5, though.

Êsw ìv

Try it


Explanation

Ê calculates the factorial of the input, s converts it to a string and back to an integer after w has reversed it, ì converts the result to an array of digits and v returns the first element.


Alternatives

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ
  • How long does this take to execute all the test cases? – Toby Speight Jun 5 at 10:17
  • @TobySpeight; that's very easy to test by following the link to try it. Note that the last 4 test cases will fail as their factorials are larger than JavaScript's max integer. – Shaggy Jun 5 at 11:30
  • So it doesn't actually solve the problem then? The question says it must succeed for 1 ≤ N ≤ 1,000,000. Other answers demonstrate that you don't need to be able to store the factorial to compute the answer. – Toby Speight Jun 5 at 12:23
  • I tried the online test, but it times out on the first test-case I tried (1000). – Toby Speight Jun 5 at 12:25

Perl 5, 36 + 10 (-p -Mbigint) = 46 bytes

$"=$_;$_*=$"while$"-=1;($_)=/(.)0*$/

Try it online!

  • The TIO version fails the first two test cases I tried: 1000000 ⇒ f (should be 4) and 100 ⇒ 7 (should be 4) – Toby Speight Feb 20 at 14:22
  • It's overflowing the size of an int. The new version works by using bigint. Performance still leaves something to be desired as it's a brute force calculation. That means it times out on TIO for larger numbers. – Xcali Feb 20 at 17:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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