You are not logged in. Please login at www.codechef.com to post your questions!

×

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;
}

asked 24 Jun '13, 19:09

anshbansal's gravatar image

1★anshbansal
5191215
accept rate: 0%

closed 24 Jun '13, 21:14

kunal361's gravatar image

4★kunal361
6.0k133272


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...

link

answered 24 Jun '13, 19:45

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

edited 24 Jun '13, 19:47

How did you even manage to find that out?

(24 Jun '13, 20:10) anshbansal1★

There are only 100 possibilities, so I tried all of them ;-)

(24 Jun '13, 20:13) betlista ♦♦3★

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)

(24 Jun '13, 20:15) anshbansal1★
1

I generated test case to get result for all, then I used your code to generate results (http://ideone.com/53vqA0), mine (http://ideone.com/d6loVk) and compared with diff (http://en.wikipedia.org/wiki/Diff) ;-)

Of course I first tried some "special" values...

(24 Jun '13, 20:26) betlista ♦♦3★

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

(24 Jun '13, 20:38) anshbansal1★

Found it. Got AC :-)

(24 Jun '13, 20:51) anshbansal1★

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

(30 Jul '13, 22:30) pnomarev5★
showing 5 of 7 show all

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

link

answered 24 Jun '13, 19:19

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

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

(24 Jun '13, 19:26) anshbansal1★

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 :)

(24 Jun '13, 19:38) kuruma3★

What wrong with my code?

include<iostream>

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;

}

(30 Jul '13, 17:43) vjozic0★

@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...:)

link

answered 30 Jul '13, 19:05

kunal361's gravatar image

4★kunal361
6.0k133272
accept rate: 21%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,491
×1,070
×856
×46

question asked: 24 Jun '13, 19:09

question was seen: 3,523 times

last updated: 30 Jul '13, 22:30