codechef :wrong answer error in smallfactorial

Question

#include<stdio.h>
int fact(int k)
{
int j,f=1;
for(j=1;j<=k;j++)
f*=j;
return f;
}
int main()
{
int t,i,n[100],s[100],j;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&n[i]);
}
for(j=0;j<t;j++)
{
s[j]=fact(n[j]);
printf("%d \n",s[j]);
}
return 0;
}

You are asked to calculate factorials of some small positive integers. Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100. Output

For each integer n given at input, display a line with the value of n! Example

Sample input: 4 1 2 5 3 Sample output: 1 2 120 6

Answer 1

Your code will give correct results for the given test cases but that doesn't prove that your code works. It is wrong is because of integer overflow. Try to calculate 100! by your program and you'll see what's the problem.

---

My answer lacked details. I'll update this to add details for an answer to the question as it stands now.

C has limitations over the the maximum and minimum size that can be stored in a variable. For doing arbitrary precision arithmetic it is usually advisable to use a bignum library as PHIFounder has suggested.

In the present case however, the use of external libraries is not possible. In this case arrays can be used to store integers exceeding the maximum value of the integers possible. OP has already found this possibility and used it. Her implementation, however, can use many optimizations.

Initially the use of large arrays like that can be reduced. Instead of using an array of 100 variables a single variable can be used to store the test cases. The use of large array and reading in test cases can give optimization only if you are using buffers to read in from stdin otherwise it won't be any better than calling scanf for reading the test cases by adding a scanf in the for loop for going over individual test cases.

It's your choice to either use buffering to get speed improvement or making a single integer instead of an array of 100 integers. In both the cases there will be improvements over the current solution linked to, on codechef, by the OP. For buffering you can refer to this question. If you see the timing results on codechef the result of buffering might not be visible because the number of operations in the rest of the logic is high.

Now second thing about the use of array[200]. The blog tutorial on codechef uses an array of 200 elements for demonstrating the logic. It is a naive approach as the tutorial itself points out. Storing a single digit at each array location is a huge waste of memory. That approach also leads to much more operations leading to a slower solution. An integer can at least store 5 digits (-32768 to 32767) and can generally store more. You can store the intermediate results in a long long int used as your temp and use all 5 digits. That simplification itself would lead to the use of only arr[40] instead of arr[200]. The code would need some additional changes to take care of forward carry and would become a little more complex but both speed and memory improvements would be visible.

You can refer to this for seeing my solutions or you can see this specific solution. I was able to take the use down to 26 elements only and it might be possible to take it further down.

I'll suggest you to put up your code on codereview for getting your code reviewed. There are many more issues that would be best reviewed there.

Answer 2

Here, your array index should start with 0 not 1 , I mean j and ishould be initialized to 0 in for loop.

Besides, try to use a debugger , that will assist you in finding bugs.

And if my guess is right you use turbo C, if yes then my recommendation is that you start using MinGW or Cygwin and try to compile on CLI, anyway just a recommendation.

There may be one more problem may be which is why codechef is not accepting your code you have defined function to accept the integer and then you are passing the array , may be this code will work for you:

#include<stdio.h>
int fact(int a[],int n)// here in function prototype I have defined it to take array as argument where n is array size.
{
  int j=0,f=1,k;
  for (k=a[j];k>0;k--)
    f*=k;
  return f;
}
int main()
{
  int t,i,n[100],s[100],j;
  setbuf(stdout,NULL);
  printf("enter the test cases\n");
  scanf("%d",&t); //given t test cases
  for(i=0;i<t;i++)
    {
      scanf("%d",&n[i]); //value of the test cases whose factorial is to be calculated
    }
  for(j=0;j<t;j++)
    {
      s[j]=fact(&n[j],t);// and here I have passed it as required 

      printf("\n %d",s[j]); //output
     }
  return 0;
}

NOTE:- After the last edit by OP this implementation has some limitations , it can't calculate factorials for larger numbers say for 100 , again the edit has taken the question on a different track and this answer is fit only for small factorials

Answer 3

above program works only for small numbers that means upto 7!,after that that code not gives the correct results because 8! value is 40320 In c language SIGNED INTEGER range is -32768 to +32767 but the >8 factorial values is beyond that value so integer cant store those values so above code can not give the right results for getting correct values we declare the s[100] as LONG INT,But it is also work only for some range