69
\$\begingroup\$

Create the shortest program or function that finds the factorial of a non-negative integer.

The factorial, represented with ! is defined as such

$$n!:=\begin{cases}1 & n=0\\n\cdot(n-1)!&n>0\end{cases}$$

In plain English the factorial of 0 is 1 and the factorial of n, where n is larger than 0 is n times the factorial of one less than n.

Your code should perform input and output using a standard methods.

Requirements:

  • Does not use any built-in libraries that can calculate the factorial (this includes any form of eval)
  • Can calculate factorials for numbers up to 125
  • Can calculate the factorial for the number 0 (equal to 1)
  • Completes in under a minute for numbers up to 125

The shortest submission wins, in the case of a tie the answer with the most votes at the time wins.

\$\endgroup\$
  • 9
    \$\begingroup\$ How many of the given answers can actually compute up to 125! without integer overflow? Wasn't that one of the requirements? Are results as exponential approximations acceptable (ie 125 ! = 1.88267718 × 10^209)? \$\endgroup\$ – Ami Feb 6 '11 at 22:43
  • 6
    \$\begingroup\$ @SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! \$\endgroup\$ – gnibbler Feb 8 '11 at 3:21
  • 5
    \$\begingroup\$ @ugoren the two-character solution to the other question uses a built-in factorial function. That's not allowed in this version of the challenge. \$\endgroup\$ – Michael Stern Jan 7 '14 at 3:18
  • 3
    \$\begingroup\$ Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? \$\endgroup\$ – sergiol Aug 24 '17 at 18:05
  • 3
    \$\begingroup\$ @sergiol Incredibly that hasn't been an issue in the last 2 years, I suspect most languages can get it done in under a minute. \$\endgroup\$ – Kevin Brown Aug 24 '17 at 21:20

173 Answers 173

2
\$\begingroup\$

Brainfuck, 56 bytes

+>,[[>+>+<<-]>[-<<[->+<<+>]<[->+<]>>>]<<[-]>[->+<]>>-]<.

Like the other Brainfuck answers, this assumes the IO directly inputs and outputs the number in/from the cell and the interpreter has infinite cells and infinite cell size. Add a byte if you want to avoid negative cells. Add another byte if you want to do it in place.

Note: In CompressedFuck, this is only ~21 bytes.

\$\endgroup\$
2
\$\begingroup\$

Python, 30 bytes

f=lambda n:n*f(n-1)if n else 1

Saves some characters by using lambda syntax and a ternary if-else.

\$\endgroup\$
  • \$\begingroup\$ This is very similar to the Python answer on the first page, and doesn't really add anything. \$\endgroup\$ – lirtosiast Jun 22 '15 at 14:51
  • \$\begingroup\$ Firstly, there are many Python answers. Secondly, which answers are on which page is dependent on how you sort the answers. Thirdly, even if my answer doesn't add anything super cool or unique, it's still different enough for me to post it as my own. Because it IS my own. I created it without reading the other answers first. \$\endgroup\$ – mbomb007 Jun 22 '15 at 18:32
  • 1
    \$\begingroup\$ There are five Python answers; two of them are exactly yours except that the authors used and/or rather than ternary or forgot to use lambda. If I had this solution, I would post it as an improvement comment on those answers due to similarity, or not post if there is no improvement. \$\endgroup\$ – lirtosiast Jun 22 '15 at 18:46
  • 2
    \$\begingroup\$ Using and/or instead of ternary is pretty different in Python for this challenge. Your feedback is appreciated, but I'm not removing my answer. This answer was posted 5 months ago and was fine. \$\endgroup\$ – mbomb007 Jun 22 '15 at 18:51
2
\$\begingroup\$

Brain-Flak, 52 bytes

Came up with the solution independently, thanks JoKing for telling me that it's possible to get 52 bytes.

<>(())<>{(({})<({<>({})<><({}[()])>}{})<>{}>[()])}<>

Try it online!


Ungolfed:

<>(())<>		# push 1 on the other stack
{			# while x:
 (
  ({})			# copy x to the 3rd stack
  <(			# push the
   {			# running total of
    <>({})<>		# top of the other stack
    <({}[()])>		# (while decrementing x)
   }
   {}			# pop redundant 0
  )<>{}>
  [()]
 )			# push x-1
}
<>

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ It's interesting that you don't always end up on the same stack at the end. Here's my own 52 byte answer if anyone else is interested. \$\endgroup\$ – Jo King May 22 '18 at 6:26
2
\$\begingroup\$

Aheui (esotope), 93 90 87 bytes

박밴내색뱅뿌뮹
숙쌕빼서빼처소
타뿌싼때산쑥희
매차뽀요@어몽

Try it online!

Nice, small, and fast code. Slightly golfed after writing explanation. I'll not change it, because it is just same code.

Explaination

Aheui is befunge-like language and (almost) every character of Aheui is operator. Part of character looks like ㅏ, ㅐ, ㅓ, ㅜ, ㅛ, ㅗ, ㅢ determines direction where next operator execute. is left-to-right, is right-to-left, is down-to-up, is up-to-down, is down-to-up, with skipping one character in two characters. is 'nothing' : keep same speed and direction.

박밴내

commend is store given number in current stack, commend is divide upmost two number in current stack. Both and store 2, so 박밴내 store 1 in current stack(default or nothing stack)

색뱅

commend change current stack. change stack to (or ) stack. commend with (like or ) get a number from STDIN. So 색뱅 get a number and store it in stack 악(ㄱ).

뿌
처

commend duplicate upmost value in current stack, and commend pop value from current stack and see if it is 0. If it is, it go to opposite direction from indicate : in here right-to-left. If it is not, it go to direction where indicate. So 뿌(\n)처 see if input is 0 or not, and go right if zero, and go left if not.

망희
소

If input is zero, here is evaluated. (from commend) First, change current stack to nothing(). commend is pop, and if used with it print value as number. halts program. So it print 1 and halt.

숙쌕빼서빼
타뿌싼때산쌕꾸
매차뽀요애애어

enter image description here

Look at this image for help. Here is main loop. is subtraction, and is multiply. move value from current stack to selected one.

Put it shortly, it get number from nothing stack(or get 1), subtract to find if it is zero, and if not zero multiply and restart loop. And if zero, go to rightmost place of code with popping one number.

Print number, then pointer go to : halt.

In one image :

AheuiChem image translated

SEL is select, MOV is move, DUP is duplicate. This image is produced by AheuiChem, Aheui development tool in Korean. Translated with paint tool of windows.

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 41

function(n,r){for(r=1;n;r*=n--);return r}

or 39 if globals are okay.

\$\endgroup\$
1
\$\begingroup\$

><>, 18 22

Launch with -v number for inputting the argument, or put it before the one.

Now also handles 0, some more intelligent direction usage, and some more space for putting numbers up to ff* or 225:

   1&:?\&n;
:-1&*&:/?=0

Old version

 1&>:&*&\
;n&\?-1 /
\$\endgroup\$
1
\$\begingroup\$

JAVA

I rarely see Java solutions here. Why is that?

    public static void main(String[] args)
 {
     int tot = 1;
 for(int i = 1;i<=5;i++)
     tot *= i;
     System.out.println(tot);
}
\$\endgroup\$
  • \$\begingroup\$ Yes, and it can calculate the factorial for 0. Put the factorial value in the loop continuation condition. i.e 5 \$\endgroup\$ – Mob Aug 6 '11 at 11:17
  • \$\begingroup\$ Java's a pretty verbose language, so it's not great for getting the lowest character count. \$\endgroup\$ – Gareth Aug 6 '11 at 13:34
  • \$\begingroup\$ @Gareth Yeah, but Brain Fuck isn't right? \$\endgroup\$ – Mob Aug 7 '11 at 19:13
  • \$\begingroup\$ You asked why you rarely see Java solutions here - it's because Java's verbose and less likely to win at code-golf. That's not to say there are no Java solutions, or that people shouldn't post Java solutions - they're just rarer for that reason. \$\endgroup\$ – Gareth Aug 7 '11 at 20:06
  • 2
    \$\begingroup\$ This is code-golf. With barely any work at all, you can significantly reduce the length by removing unnecessary whitespace and using 1-letter variable names \$\endgroup\$ – Cyoce Feb 5 '16 at 6:30
1
\$\begingroup\$

Scala, 39

def f(x:BigInt)=(BigInt(1)to x).product
\$\endgroup\$
1
\$\begingroup\$

Ruby, 19

[1,*2..n].inject :*

The extra hardcoded 1 at the beginning makes it work for when n=0.
Ruby auto-converts to BigInt after a certain point, so it has 100% accuracy.

\$\endgroup\$
1
\$\begingroup\$

In Q (18 characters)

f:{(*/)9h$1+til x}

Computes in less than one millisecond.

q)\t f 125
0
\$\endgroup\$
  • \$\begingroup\$ f:{prd 1f+til x} for 16. f:{prd 1f+(!)x} for 15. \$\endgroup\$ – streetster Sep 13 '17 at 7:44
1
\$\begingroup\$

Mathematica

f = If[# > 0, # f[# - 1], 1] &
f[125] = 188267.....
\$\endgroup\$
1
\$\begingroup\$

C++11 (35 chars)

Here's the function version:

int f(int x){return x?x*f(x-1):1;}

C++11 template version (103 chars)

And here's the template version:

template<int I>struct f{static const int v=I*f<I-1>::v;};template<>struct f<0>{static const int v=1;};
\$\endgroup\$
1
\$\begingroup\$

Golfscript — 16

{.!+,{(}%{*}*}:f

The way I handle 0! is to do this trick: .!+:

  • 0 + 0! = 0 + 1 = 1
  • a + a! = a + 0 = a (for every a != 0)

or:

{),{)}%);{*}*}:f

Here, I start of by increasing the argument by 1. But before I factor the array, I drop the last element.

\$\endgroup\$
1
\$\begingroup\$

PHP, 41

function f($i){return $i==1?:$i*f($i-1);}
\$\endgroup\$
1
\$\begingroup\$

Julia - 17

!n=n>1?n*!(n-1):1

This defines !n as !(n-1)*n if n>1, 1 otherwise. To make it work with big numbers you just need to make "n" a BigInt type (build in Julia).

And if its permitted (13 chars.):

!n=gamma(n+1)

with gamma equals to:

gamma

In the particular case that z its an integer the gamma function would be equal to:

enter image description here

Like its not a build in factorial it must not break the rules, but Im not posting it as solution just in case it does.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6) - 17 Characters

f=x=>x?x*f(x-1):1

Or:

f=x=>!x||x*f(x-1)

JavaScript - 17 Characters (not a function)

for(a=1;n;)a*=n--

Assumes that the variable n contains the number you want the factorial for and outputs the answer to the console and stores it in the variable a.

\$\endgroup\$
  • \$\begingroup\$ But will this provide the full numeric value of 125!? \$\endgroup\$ – WallyWest Nov 5 '14 at 1:37
  • \$\begingroup\$ @WallyWest yes, JavaScript has only one numeric type, Number. It is not arbitrary precision, but it can hold up to 170! Before overflow, at which point it is said to be Infinity. JS is weird?, but it is actually helpful in this case. \$\endgroup\$ – Cyoce Feb 5 '16 at 6:51
  • \$\begingroup\$ Wow... I just looked at the similarities between my code and yours. Ours are basically the same. \$\endgroup\$ – Drew Christensen Jun 8 '16 at 19:30
1
\$\begingroup\$

Mathematica – 46 characters

f[x_]:=Integrate[(x+1)^(t-1)Exp[-x-1],{t,0,∞}]

This is using the integral definition of the Gamma Function.

\$\endgroup\$
  • \$\begingroup\$ I like this solution! \$\endgroup\$ – lambruscoAcido Sep 9 '14 at 10:45
1
\$\begingroup\$

Ruby: 22 characters

n.downto(1).reduce(:*)
\$\endgroup\$
1
\$\begingroup\$

Powershell, 31

$a=1;$args[0]..1|%{$a=$_*$a};$a

usage

powershell -nologo .\fact125.ps1 0
0
powershell -nologo .\fact125.ps1 1
1
owershell -nologo .\fact125.ps1 5
120
powershell -nologo .\fact125.ps1 125
1.88267717688893E+209
\$\endgroup\$
  • \$\begingroup\$ This doesn't account for 0!=1. You can use the Invoke-Expression command to evaluate on-the-fly, and then use bool casting to select the appropriate answer -- try param($a)$b=1..$a-join'*'|iex;($b,1)[!$a] for 41 bytes \$\endgroup\$ – AdmBorkBork Nov 23 '15 at 20:13
  • 1
    \$\begingroup\$ Actually, we can move the |iex and skip the $b entirely -- 37 Bytes for param($a)((1..$a-join'*'),1)[!$a]|iex \$\endgroup\$ – AdmBorkBork Nov 23 '15 at 20:38
1
\$\begingroup\$

Bash/coreutils/dc, 25

dc<<<"1 `seq -f%g* $1`p"

This forms a dc script and evaluates it. So ,with input of 5, we evaluate

1 1*
2*
3*
4*
5*p

It took my machine 2.05 seconds to compute 10000! here (that's factorial ten-thousand, with 36693 digits), so seems to scale reasonably well. For the zero case, seq produces no output, so the dc script is just 1 p which produces the correct output 1.

\$\endgroup\$
1
\$\begingroup\$

APL (13)

∇R←F X
R←×/ιX
∇

May need a ⎕IO←1 line to be sure ι starts at 1 - it's been awhile since I last used APL.

\$\endgroup\$
  • \$\begingroup\$ ⎕IO←1 is default in many APLs. Also, you can save 3 bytes: Remove the and the last line break, giving the ⎕CR instead of the ⎕VR. Typo: * should be ×. The former is Power: n*2 = n². \$\endgroup\$ – Adám Jan 25 '16 at 14:35
1
\$\begingroup\$

PlatyPar, 8 bytes

c?1,_p\1

Try it online!

Explanation:

c?        ## if (n != 0)
  1,_p     ## product [1..n]
       \  ## else
        1  ## 1
\$\endgroup\$
  • \$\begingroup\$ This does not seem to handle the special 0 case. \$\endgroup\$ – Mama Fun Roll Jan 26 '16 at 4:04
  • \$\begingroup\$ @ՊՓԼՃՐՊՃՈԲՍԼ oops, I completely forgot. Adding... \$\endgroup\$ – Cyoce Jan 26 '16 at 4:46
1
\$\begingroup\$

JavaScript, 34 bytes

function f(n){return n?n*f(n-1):1}

(or)

function f(n){return n?n*f(--n):1}

Explanation

Function takes in a value, returns itself multiplied by
if n != 0: the same function on the number decreased by one
if n == 0: 1

The final f(0) returns first with 1, times 1, times 2, etc.

Terminator removed, may upset use strict.

\$\endgroup\$
  • \$\begingroup\$ There were already some similar answers but uses ES6. \$\endgroup\$ – jimmy23013 Jan 26 '16 at 22:42
1
\$\begingroup\$

Japt, 8 bytes (non-competing)

This answer is non-competing because Japt was created long after this challenge.

UòJ ¤r*1

Test it online!

How it works

UòJ ¤r*1   // Implicit: U = input integer                5
UòJ        // Create the inclusive range [-1..U].        [-1, 0, 1, 2, 3, 4, 5]
    ¤      // Slice off the first two items.             [1, 2, 3, 4, 5]
     r*1   // Reduce by multiplication, starting at 1.   1*1=1*2=2*3=6*4=24*5=120
           // Implicit output                            120
\$\endgroup\$
  • \$\begingroup\$ This does not handle the zero case correctly (0! should return 1). \$\endgroup\$ – Mama Fun Roll Jan 27 '16 at 3:40
  • \$\begingroup\$ @ՊՓԼՃՐՊՃՈԲՍԼ Thanks, fixed now. \$\endgroup\$ – ETHproductions Jan 27 '16 at 23:21
  • \$\begingroup\$ I know this is old but, wouldn't á be enough? \$\endgroup\$ – Luis felipe De jesus Munoz Aug 7 '18 at 17:51
  • \$\begingroup\$ @LuisfelipeDejesusMunoz I think you mean l, but yes :-) \$\endgroup\$ – ETHproductions Aug 8 '18 at 15:30
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 9 chars / 19 bytes (noncompetitive)

+!ï⋎⨴⩤⁽1ï

Try it here (Firefox only).

Ay, 19th byte!

Great thing about this is that it also calculates factorials up to 171 instantly without returning Infinity.

Bonus solution!

+!ï⋎⨴МĂ⩤⁽1ï

Try it here (Firefox only).

This one allows you to calculate past 171 without getting Infinity. Still superbly fast!

\$\endgroup\$
  • \$\begingroup\$ Mind explaining how this gets around Infinity? :) \$\endgroup\$ – ETHproductions Jan 27 '16 at 18:30
  • \$\begingroup\$ МĂ is math.js's bignumber function. \$\endgroup\$ – Mama Fun Roll Jan 27 '16 at 23:07
1
\$\begingroup\$

Lua, 47 bytes

function f(n)return(n<1 and 1 or n*f(n-1))end
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 16 bytes

n->prod(i=2,n,i)

The shortest answer would be the native ! which is disallowed.

\$\endgroup\$
1
\$\begingroup\$

PHP

Short, 58

<?$r=$i=$argv[1];while($i>1){$i--;$r=$r*$i;}echo($r==0?1:$r);

Tests

0 -> 1

1 -> 1

5 -> 120

125 -> 1.8826771768889E+209

170 -> 7.257415615308E+306

171 -> INF

Executes in microseconds.

Ungolfed

<?php
$r = $i = $argv[1]; // Set $r and $i to Arg.
while($i > 1) // Calculate while $i bigger than 1
{
    $i--; // Decrement $i (so it's not infinite)
    $r = $r * $i; // Calculation the Factorial
 }
 echo ($r==0 ? 1: $r); // Output and make 0! = 1
 ?>

Slighty Longer, 86

<?$r=$i=(isset($argv[1])?$argv[1]:0);while($i>1){$i--;$r=$r*$i;}echo($r==0?1:$r)."\n";

Improvements

  • Output with \n
  • Doesn't throw error if no arg defined
\$\endgroup\$
1
\$\begingroup\$

DUP, 19 bytes

[$[$1-a;!*][%1]?]a:

Try it here!

A recursive lambda that leaves result on the stack. Usage:

6[$[$1-a;!*][%1]?]a:a;!

Explanation

[               ]a: {set a to lambda}
 $                  {check if top of stack >0}
  [       ][  ]?    {conditional}
   $1-a;!*          {if so, top of stack *a(top of stack -1)}
            %1      {otherwise, replace top of stack with 1}
\$\endgroup\$
1
\$\begingroup\$

Hoon, 29 bytes

|=(@ (reel (gulf [1 +<]) mul)

Hoon's native number is a bignum, so it works fine with 125 (or even 2000). It also correctly gives 1 for 0.

It uses +< in order to access the sample of the gate. This is axis navigation syntax: It means to access the tail of the subject, and then the head, which is where the sample is stored in the binary tree model Hoon uses.

Urbit drops you into a shell and Hoon REPL when you start it, :dojo. To test this, simply enter %. 125 on one line and then the snippet for 125! Note there are two spaces between the dot and 1.

\$\endgroup\$
  • \$\begingroup\$ Hoon is a beautiful mystery. \$\endgroup\$ – Lynn Mar 1 '16 at 1:10
  • 1
    \$\begingroup\$ It's a surprisingly nice language to code in! It takes a little bit to learn all the runes, but you don't even need to internalize them to read it since they belong in "families" based on the first symbol. The fact it's strongly typed and has a novel type system is just icing on the cake. \$\endgroup\$ – RenderSettings Mar 1 '16 at 1:36

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.