I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Return the Factorial

08.02.2012
| 4136 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Return the Factorial

Write a function which will return the factorial of a number n. Factorial is the product of the sequence  n, n-1, n-2 .... 1.  And remember that the factorial of 0 is actually 1. 


Catch up on all our previous puzzlers here

Comments

Stelian Galmati replied on Thu, 2012/08/02 - 1:57am

public int factorial(int n) {

if (n == 0) {

return 1;

}

return n * factorial(n - 1);

}

Alexey Grigorev replied on Thu, 2012/08/02 - 2:11am

These puzzlers used to be difficult

Vijay Nathani replied on Thu, 2012/08/02 - 3:03am

Groovy code

def factorial(n) {
	def fact = 1; 
	n.times { fact *= it.next() }
	fact
}
println factorial(3)

 

Attila Király replied on Thu, 2012/08/02 - 3:18am in response to: Alexey Grigorev

It is always possible to make it more difficult. I noticed that in the world of many cores people almost never post a multi threaded solution to these puzzlers.

Folkert Meeuw replied on Thu, 2012/08/02 - 7:54am

 Tested with -1=>,0=>1,4=>24,10=3628800,20=>-2102132736,34=>0

public class Factorial
{
        public int factorial(int n)
        {
                if (n == 0)
                        return 1;
                return n*factorial(n-1);
        }
        public static void main(String[] args)
        {
                Factorial f = new Factorial();
                System.out.println("factorial of the number " +args[0] + " is "+ 
                f.factorial(Integer.parseInt(args[0])));
        }
}

matt inger replied on Fri, 2012/08/03 - 7:43am

Java code.     Assuming we're bound to long values, we can precompute, since there's a limited range of inputs which can produce results which won't overflow a long value.

 

  private static long fact[] = {
            1L,
            1L,
            2L,
            6L,
            24L,
            120L,
            720L,
            5040L,
            40320L,
            362880L,
            3628800L,
            39916800L,
            479001600L,
            6227020800L,
            87178291200L,
            1307674368000L,
            20922789888000L,
            355687428096000L,
            6402373705728000L,
            121645100408832000L,
            2432902008176640000L
    };
 
    public static long factorial(long n) {
        if (n < 0) return 0;
        if (n >= fact.length) throw new IllegalArgumentException("value is out of range");
        return fact[(int)n];
    }

 

 

Here's another non-recursive version:

 

    public static long factorial(int n) {
        if (n<0) return 0;
        long fact[] = new long[n+1];
        fact[0] = 1L;
        for (int i=1;i<=n;i++) {
            fact[i] = (long)i * fact[i-1];
            if (fact[i] < fact[i-1]) throw new IllegalArgumentException("overflow detected.");
        }
        return fact[n];        
    } 

 

Nils Rudolph replied on Thu, 2012/08/02 - 8:22am

Java with Fork/Join Framework and BigInteger

 

import java.math.BigInteger;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class FactorialAction extends RecursiveAction {

	private static final BigInteger THRESHOLD = BigInteger.valueOf(10);
	
	private final BigInteger start;
	private final BigInteger end;
	
	private BigInteger result = BigInteger.ONE;
	
	public FactorialAction(BigInteger start, BigInteger end) {
		this.start = start;
		this.end = end;
	}
	
	@Override
	protected void compute() {
		if  (start.subtract(end).compareTo(THRESHOLD)  <= 0) {
			computeDirectly();
		} else {
			BigInteger mid = end.add(start.subtract(end).divide(BigInteger.valueOf(2)));

			
			FactorialAction left = new FactorialAction(start, mid);
			FactorialAction right = new FactorialAction(mid, end);
			
			invokeAll(left, right);
			result = left.getResult().multiply(right.getResult());
		}
	}

	private void computeDirectly() {
		
		for (BigInteger i = start; i.compareTo(end) > 0; i = i.subtract(BigInteger.ONE)) {
			result = result.multiply(i);
		}		
	}

	public BigInteger getResult() {
		return result;
	}
	
	public static void main(String[] args) {
		BigInteger n = BigInteger.valueOf(500);
		
		ForkJoinPool pool = new ForkJoinPool();
		FactorialAction factorial = new FactorialAction(n, BigInteger.ONE);
		pool.invoke(factorial);
		
		System.out.println(factorial.getResult());
		
	}

Kris Scorup replied on Thu, 2012/08/02 - 12:29pm

Oracle SQL. 83 is the max number you can supply before causing an ORA-01426: numeric overflow exception. There may be some rounding errors due to using logarithms. 
select round(exp(sum(ln(rownum)))) factorial
from   dual
where  :what_number >= 0
connect by rownum <= :what_number

Folkert Meeuw replied on Thu, 2012/08/02 - 1:29pm in response to: Nils Rudolph

@Nils, your code is Java™ Platform, Standard Edition 7 specific. I've to read the article http://java.dzone.com/articles/javas-fork-join-framework first

Charlie Mordant replied on Fri, 2012/08/03 - 3:10am

private Set<int, Long> cache = new  HashSet<int, Long>();

public int factorial(int n) {

if (n == 0) {

return 1;

}else if (cache.containsKey(n)){ return cache.get(n);]

else {

int fact =  n * factorial(n - 1);

cache.put (n,  fact);

return fact;

}

}

 

Jagannathan Asokan replied on Fri, 2012/08/03 - 7:44am

#Ruby

def factorial(n)
  if n==0
    return 1
  else
    n * factorial(n-1)
  end
end


p factorial(0)
p factorial(20)
p factorial(200)
p factorial(999)

 

1
2432902008176640000
788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.