Power By 专否社区

Factorials Challenge.(Beginner's Challenge)

Go To StackoverFlow.com

2

I tried the following challenge:

Given the first few factorials:

1! = 1

2! = 2 x 1 = 2

3! = 3 x 2 x 1 = 6

4! = 4 x 3 x 2 x 1 = 24

What is the sum of the first 15 factorials, NOT INCLUDING 0!?

My solution in Java is the following: 

public class Factorial
{
   public static void main(String[] args)
   {
     int sum = 0;    
     int multi = 1;
        for (int i=1;i<=15;i++)         
        {
        multi = multi*i;
        sum = multi+sum;     
        }     
     System.out.print(sum);
   }
}

I verified the solutions for the first 7 factorials but will it work for the first 15?

2012-04-04 18:36
by NoName
HINT: For an elegant solution - use a recursive method - Che Jami 2012-04-04 18:38
well is it working - talnicolas 2012-04-04 18:38
@Che For a badly performing solution, use a recursive metho - David Heffernan 2012-04-04 18:39
question in a question. it's like inception :) i did not get what u mean. so it doesnt work after 7th - anvarik 2012-04-04 18:41
What makes you think it might not work for 15 - David Heffernan 2012-04-04 18:41
@CheJami Recursive factorial is not elegant. It is actually the worst recursive function you can write. It works well for small numbers but not for larger ones, and factorial increases exponentially so the set of numbers that factorial actually works well is very, very small - darksky 2012-04-04 18:44
Recursive factorial is not as terrible these comments indicate. It can be done with O(n) complexity for time and memory. The iterative solution has O(1) memory usage and O(n) time complexity. I wonder whether people are thinking of recursive Fibonacci sequence calculation, which is a textbook example of poor performance for a recursive algorithm - Odrade 2012-04-04 19:00
Wouldn't recommend recursive solution in Java, but it'd be insane not to use recursion in a language that utilizes a tail recursive optimization such as Scheme or some other functional programming languages. It's not recursion that's the issue, it's the language, and it's implementations - JayC 2012-04-04 19:10

4

No, its not working for 15. Use long. Also, you could move the print statement inside the loop, to check from where it starts failing. I guess in this case it's 13.

2012-04-04 18:43
by Gyanendra Singh
It starts failing with number 13, long does its job - NoName 2012-04-04 18:54

6

It will not work for the first 15 factorials because of integer overflow. The correct answer is 1401602636313, which exceeds Java's int bound of 2147483647. You could either use a long which has a bound of 9223372036854775807 or a BigInteger.

2012-04-04 18:40
by Jeffrey
Yes it works with long, i forgot this overflow. I found the same answer: 1401602636313 - NoName 2012-04-04 18:56

1

That

public static void printFactorials (int max) {
    long fac = 1;
    long sum = 0;
    for (int i = 1; i <= max; fac *= ++i) {
        System.out.println(String.format("Factorial(%2d)=%d", i, fac));
        sum += fac;
    }
    System.out.println(String.format("Sum of Factorials(1 to %2d)=%d", max, sum));
}

gives you

Factorial( 1)=1
Factorial( 2)=2
Factorial( 3)=6
Factorial( 4)=24
Factorial( 5)=120
Factorial( 6)=720
Factorial( 7)=5040
Factorial( 8)=40320
Factorial( 9)=362880
Factorial(10)=3628800
Factorial(11)=39916800
Factorial(12)=479001600
Factorial(13)=6227020800
Factorial(14)=87178291200
Factorial(15)=1307674368000
Sum of Factorials(1 to 15)=1401602636313

long starts to fail at 21, next step is BigInteger

public static void printRlyBigFactorials (int max) {
    BigInteger fac = BigInteger.ONE;
    BigInteger sum = BigInteger.ZERO;
    for (int i = 1; i <= max; ++i) {
        fac = fac.multiply(BigInteger.valueOf(i));
        sum = sum.add(fac);
        System.out.println(String.format("Factorial(%2d)=%d", i, fac));
    }
    System.out.println(String.format("Sum of Factorials(1 to %2d)=%d", max, sum));
}

That will work almost indefinitely and can give you fancy results like:

Sum of Factorials(1 to 500)=
1222581999810786173488382263893486121736784649845260488587055662127413631697
9142090995417259894466676137016242713788312106218384177808117660024733369428
7060019503701220190523381023699528466605036804597249531428694859689049295904
5138704466475196055082304091214424335155644013903958356823605973150159110295
5787828433482529258832635575855564789877227459384652114477297831606218655683
9245588828671235437927278554210732477499719243692398907465554636521289870187
5799458234466791378320221140358905721655475503366304295011345436395868843079
5463780536087239619245051615759218253091986494512882003123090598805090122753
7135918455294416676103707115038417384516670399033063650562275830354903359872
0775172343137459008549361297203752431405977559950082400276439557196120290170
5516606073135650288107937474531851451830365876392678959480905477335825506233
3795849463603798966643420966668878072957663827751761832039623225350606860709
6479320263132522604054741925038640750661849690108363701190203548476572823422
7743271977187818002695582046473911765828511673121820261887951566200568565033
40092247479478684738621107994804323593105039052556442336528920420940313
2012-04-04 18:54
by zapl
Exactly. Integer overflow was my mistake by using int instead of long - NoName 2012-04-04 19:13
Ads