SPOJ Small Factorial program in C

Question

My code is showing 'wrong output' in SPOJ, although it's running without trouble in my compiler.

The code for the program is :

#include<stdio.h>

int factorial(int);

int main(){
    int a[100],t,n,i;
    scanf("%d",&t);
    for(i=0;i<t;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<t;i++){
        printf("%d",factorial(a[i]));
        printf("\n");   
    }
    return 0;
}

int factorial(int n){
    if(n==0){
        return 1;
    }
    else if(n==1){
        return 1;
    }
    else{
        return n*factorial(n-1);
    }
}

According to the problem specification, n <= 100. Consider how large the number 100! is. Does it fit in an `int`? — njuffa, Feb 05 '15 at 19:09
You can also try a non recursive function: `int result = 1; for(int i = n; i > 1; i--) result*=i;` although it appears right. Without seeing your 'wrong output' I can't tell. — MiltoxBeyond, Feb 05 '15 at 19:15
possible duplicate of [SPOJ -Small factorials](http://stackoverflow.com/questions/27874823/spoj-small-factorials) — phuclv, Feb 06 '15 at 09:02

yellowantphil · Accepted Answer · 2015-02-05T20:22:31.290

5

Your program is getting integer overflow. You need at least 66 bytes to store 100! exactly. An unsigned long long int is usually 8 bytes, and can store up to 1.8 × 10¹⁹. 100! is about 9.3 × 10¹⁵⁷.

You need another way to calculate this value, or use a different language. You could try storing the values in a double or long double, but it isn't going to be exact, so I doubt it will satisfy SPOJ.

edited Feb 05 '15 at 20:22

answered Feb 05 '15 at 20:15

yellowantphil

1,483
5
21
30

to be exact, it needs [~524.765 bits](http://www.wolframalpha.com/input/?i=log+base+2+of+%28100!%29) to store 100! – phuclv Feb 06 '15 at 09:00

score 3 · Answer 2 · answered Feb 06 '15 at 08:40

100! is a huge number (around 160 digits I think). "long long" can store at max 19 digits. You can do any of the following to solve this question :

Use a language that supports very big integers like java or python.
Create your own biginteger type code for languages like c/c++. Use an array to represent the entire huge number, with every index of the array storing only one digit of the number. For ex, if the number is 123, index [0] stores digit 1, index[1] stores digit 2 and index[2] stores digit 3. (You may store them in the reverse order depending on your choice).

The code you have put up suffers from integer overflows. Using double/long double will not work since it will suffer from precision loss.

SPOJ Small Factorial program in C

2 Answers2