×

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

 1 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 #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 51●9●12●15 accept rate: 0% 4★kunal361 6.0k●13●32●72

 1 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... answered 24 Jun '13, 19:45 16.9k●49●115●225 accept rate: 11% How did you even manage to find that out? (24 Jun '13, 20:10) There are only 100 possibilities, so I tried all of them ;-) (24 Jun '13, 20:13) 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) 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) Thanks. Now I am left scratching my head looking at the code and thinking where it went wrong. ;) (24 Jun '13, 20:38) Found it. Got AC :-) (24 Jun '13, 20:51) 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

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)

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) 3★

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) 0★
 0 @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...:) answered 30 Jul '13, 19:05 4★kunal361 6.0k●13●32●72 accept rate: 21%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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