78
\$\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\$
  • 13
    \$\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
  • 6
    \$\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
  • 5
    \$\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
  • 4
    \$\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

185 Answers 185

1 2
3
4 5
7
2
\$\begingroup\$

Sage, 19 bytes

For some reason, Guido hates prod(). But, Sage supports it:

f=lambda n:prod(1..n)

edit: just had a statement previously, not a function

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

Scheme - 33 characters

Improved answer using an unnamed procedure and the λ symbol.

(λ(n)(if(= 0 n)1(* n(!(- n 1)))))

Old 40 character answer below

(define(! n)(if(= 0 n)1(* n(!(- n 1)))))

The white-space requirement is almost as much of a problem as the brackets for bloating things in scheme.

Testing:

> ((λ(n) (if(= 0 n)1(* n(!(- n 1))))) 0)
1
> ((λ(n) (if(= 0 n)1(* n(!(- n 1))))) 125)
188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ what about removing the space between define and (! n) \$\endgroup\$ – ogogmad Oct 13 '15 at 21:49
  • \$\begingroup\$ Thanks NaN - can actually remove a lot of spaces so 47 down to 40. \$\endgroup\$ – Penguino Oct 13 '15 at 22:12
  • \$\begingroup\$ Doesn't work for me (the lambda one) - ! is undefined (running in DrRacket 6.4) \$\endgroup\$ – kronicmage Jun 9 '16 at 13:30
2
\$\begingroup\$

Common Lisp, 38 bytes

Disclaimer: I'm not responsible for any traumatic effect caused by the extreme density of parentheses. It's the language specification's fault.

(defun a(b)(if(< b 2)1(*(a(- b 1))b)))

Ungolfed & explained:

(defun a (b)                               ;Define a function called "a". It has one parameter called "b"
            (if (< b 2)                    ;If b is a number that is smaller than 2 (0 and 1 satisfy this)
                       1                   ;Return 1
                        (* (a (- b 1)) b)));Otherwise, return a(b-1) multiplied by b
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi, your solution does not handle the input value '0'; you should modify the code as follows: (defun a(b)(if(= b 0)1(*(a(- b 1))b))). \$\endgroup\$ – PieCot Jun 6 '16 at 21:47
  • \$\begingroup\$ You can save a byte by using (1- b) instead of (- b 1) \$\endgroup\$ – djeis Apr 12 '17 at 16:40
2
\$\begingroup\$

PHP, 39 bytes

<?=array_product(range(1,$argv[1]))?:1;

breakdown

<?=                          // 4. print result
    array_product(           // 2. get product of the elements - special: 0
        range(1,$argv[1])    // 1. build array from 1 to N - special: [1,0]
    )
    ?:1                      // 3. special: if falsy, return 1
;
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ for($p=1;$i++<$argn;)$p*=$i;echo$p; is shorter and <?=array_product($argn?range(1,$argn):[]); is a more interesting way \$\endgroup\$ – Jörg Hülsermann Jul 9 '17 at 0:41
2
\$\begingroup\$

CJAM 9

I'm pretty sure this mmets all requirements. It ran on the online compiler for 125 is far less than a second.

1ri,{)*}%

It works as follows:

1         puts 1 on stack
ri        accepts input as integer
,         creates list of all non negative integers less than input
{         start block
          increments integer by 1
          multiplies current product by integer, current product starts with 1
}         repeat block for each element in list
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ ri,1f+:* is even shorter \$\endgroup\$ – kaine Nov 4 '14 at 22:01
  • \$\begingroup\$ Can you remove the -? It's throwing off the leaderboard snippet, thinks you're at negative 9 bytes. \$\endgroup\$ – Pavel Jan 19 '17 at 2:10
2
\$\begingroup\$

Python, 25 bytes

f=lambda x:x<2or x*f(x-1)

Try it online!

This is a recursive lambda. It returns True if the factorial is 1 (inputs 1 and 0), but that's allowed by meta.

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

Ruby, 22 bytes

n.downto(1).inject(:*)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Unfortunately, this doesn't work for 0, so you probably have to add a ternary operator. \$\endgroup\$ – Martin Ender Nov 29 '14 at 20:05
  • \$\begingroup\$ n.downto(1).inject(1,:*) \$\endgroup\$ – histocrat Jul 24 '15 at 17:12
  • \$\begingroup\$ Or in fact (1..n).inject 1,:* seems to work fine. \$\endgroup\$ – histocrat Jul 24 '15 at 17:14
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.

| improve this answer | |
\$\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
  • 3
    \$\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!

| improve this answer | |
\$\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\$

Keg, 16 bytes

(:|:1-)_(!1-|*).

This takes a top-of-stack item and returns [0..top]. Then, it discards the 0. After that, it multiplies everything in the stack, returning the factorial. (This is indeed too long.)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nicely golfed, I gave my own shot at this but was only able to get 18 bytes, +1 \$\endgroup\$ – EdgyNerd Aug 10 '19 at 11:38
  • \$\begingroup\$ I'm getting an error running that code on TIO. \$\endgroup\$ – pppery Sep 25 '19 at 20:38
  • \$\begingroup\$ Run this in an old version. (Works for most of my Keg answers) \$\endgroup\$ – user85052 Sep 25 '19 at 22:42
2
\$\begingroup\$

Python 3, 30 Bytes

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

125! took less than 1 second to do on IDLE and TIO.

How it works: the function f returns n*f(n-1) if n is not 0 and it returns 1 otherwise, the definition of a factorial.

Try it online!

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

JavaScript (Node.js), 17 bytes

Recursion. Usage of arrow function declaration and OR operator that checks whether x is 0 (if not, continue multiplying).

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

Try it online!

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

JavaScript, 41

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

or 39 if globals are okay.

| improve this answer | |
\$\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 /
| improve this answer | |
\$\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);
}
| improve this answer | |
\$\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
  • 3
    \$\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
| improve this answer | |
\$\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.

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

In Q (18 characters)

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

Computes in less than one millisecond.

q)\t f 125
0
| improve this answer | |
\$\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\$

F# based on cfern's 63 36 characters

His didn't work on 125 for me. Adapted to use BigInteger

let f n:BigInteger=Seq.fold(*)BigInteger.One{BigInteger.One..n}

Edit: I just realized that double works too.

let f n:double=Seq.fold(*)1.{1.0..n}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 63 -> 36 is simply beautiful. "I reverse the floating point usage, you reverse your byte count!" \$\endgroup\$ – val says Reinstate Monica Sep 30 at 19:00
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;};
| improve this answer | |
\$\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.

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

PHP, 41

function f($i){return $i==1?:$i*f($i-1);}
| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

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

Ruby: 22 characters

n.downto(1).reduce(:*)
| improve this answer | |
\$\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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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 2
3
4 5
7

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.