Small Factorials - C Code working on PC but wrong answer on codechef

For the problem Small Factorials I wrote the following C Code. It is working on my PC. I cross-checked the answer for 100! with a Python Script so answer is correct. I don’t have any idea why this is giving wrong answer.

I am using an integer array to store the digits. 4 digits at each array index. Lowest 4 digits at ans[0], next 4 at ans1 and so on.

What’s wrong here?

#include<stdio.h>

#define LIMIT 10000
#define ANS_SIZE 40

int main()
{
    int tests, num, ans[ANS_SIZE];
    register short int i, j, k;
    long temp;

    scanf("%d", &tests);
    for(k = 1; k <= tests; k++)
    {
        scanf("%d", &num);
        ans[0] = 1;
        for(i = 1; i < ANS_SIZE; i++)
            ans[i] = 0;

        for(i = 2; i <= num; i++)
        {
            ans[ANS_SIZE - 1] *= i;
            for(j = ANS_SIZE - 2 ; j >= 0 ; j--)
            {
                temp = ans[j] * i;
                ans[j] = temp % LIMIT;
                ans[j + 1] += temp/LIMIT;
            }
        }

        for(i = (ANS_SIZE - 1); i >= 0; i--)
            if(ans[i] != 0)
                break;

        printf("%d", ans[i]);
        i--;
        for(; i >= 0; i--)
        {
            if(ans[i] > 999)
                printf("%d", ans[i]);
            else if(ans[i] > 99)
                printf("0%d", ans[i]);
            else if(ans[i] > 9)
                printf("00%d", ans[i]);
            else if(ans[i] > 0)
                printf("000%d", ans[i]);
            else
                printf("0000");
        }

        printf("\n");
    }
    return 0;
}
1 Like

Hello,

It seems that your code is actually correct in terms of its logic, but, I suggest you retry writing it using the trick of storing only one digit at each array position!

The main reason for this is that it’s simple for you to do the arithmetics if you manipulate a single digit at a time, also due to carry.

Best regards,

Bruno

Good one, your code returns for 67

364711109181886852882498590966054644271676353140495245937016284100267962436943872000000000000000

while correct answer is

36471110918188685288249859096605464427167635314049524593701628500267962436943872000000000000000

That’s the only mistake for all 100 factorials possible as input…

1 Like

@vjozic…factorials achieve large values…double can store these values…BUT there is a loss of precision…so u need to use an array of integers to store such high numbers…u can store few digits of the factorial in each cell like…

1!=|1|
2!=|2|
3!=|6|
4!=|2|4|
5!=|1|2|0|

it is like making your own datatype…hope this helps…:slight_smile:

Is there some kind of problem with the codechef judge in this problem? Otherwise the operations are actually simpler using this approach.

I don’t think so… There might be something you are not taking into account, some special case, possibly related to number of zeroes or some extra newline… That’s why doing the arithmetics with 1 digit at a time is safer, as it gives you more control :slight_smile:

How did you even manage to find that out?

There are only 100 possibilities, so I tried all of them :wink:

By hand or scripting? How? It was frustrating enough to cross-check the answer of 100! by hand (even when I had the actual answer)

I generated test case to get result for all, then I used your code to generate results (53vqA0 - Online C++ Compiler & Debugging Tool - Ideone.com), mine (d6loVk - Online Java Compiler & Debugging Tool - Ideone.com) and compared with diff (diff - Wikipedia) :wink:

Of course I first tried some “special” values…

1 Like

Thanks. Now I am left scratching my head looking at the code and thinking where it went wrong. :wink:

Found it. Got AC :slight_smile:

What wrong with my code?

#include
using namespace std;

int main()
{
double n[100], fact[100];
double x,y,t,f;

cin>>t;

for(int i=0;i<t;i++)
{
	cin>>n[i];
}

y=t;
while(t!=0)
{
	for(int i=0;i<y;i++)
	{
		x=n[i];
		f=1;
		for(int j=1;j<=x;j++)
		{
			f=f*j;
		}
		fact[i]=f;
	}
	
	t--;
}

for(int k=0;k<y;k++)
{
	cout<<fact[k]<<endl;
}
return 0;

}

temp = ans[j] * i;
ans[j] = temp % LIMIT;
ans[j + 1] += temp/LIMIT;

After the last line ans[j+1] could become more than LIMIT, which will result in WA