Hello all,
It is a great technique to store factorial in an array.But how to use it in calculation.Suppose we need to calculate combination of n and r(nCr) and say n is 1000 and r is 100. Then how to use these factorial stored in array.
JAVA:
import java.util.Scanner;
import java.math.BigInteger;
class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int T;
T=sc.nextInt();
while(T>0){
int n, c;
BigInteger inc = new BigInteger(“1”);
BigInteger fact = new BigInteger(“1”);
n = sc.nextInt();
for (c = 1; c <= n; c++) {
fact = fact.multiply(inc);
inc = inc.add(BigInteger.ONE);
}
System.out.println(fact);
T–;
}
}
}
There is one more solution . Use long double and while printing write cout.precision(200)<<answer;
#include
#include
using namespace std;
long double fact(long double num){
if(num==1)
return 1;
else{
return num* fact(num-1);
}
}
int main(int argc, char * argv[]){
int T;
cin>>T;
while(T–){
long double num,ans;
cin>>num;
cout.precision(200);
ans=fact(num);
cout<<ans;
cout<<’\n’;
}
return 0;
}
// This solution gives the same answer. gcc4.8.1
Thanks I learned this now hehe.
Thanks a lot, a very very well explained topic. This tutorial really helped…!!
So I had anyways, written my own after reading this post; difference is that I have used char array(char[]). My program can easily calculate factorial up to 15000. 15000! is calculated in 2.00 sec to 2.07 seconds(according to Ideone).
I believe it can further be optimized. I am looking for a code which lets me easily calculate (10^9)! My search is on. One thought I got is to trim the trailing zeros, after 900 or 1000. This can significantly reduce calculations. While printing the result, the number of appending zeros can be calculated from a different way. 15000! contains something 3700 trailing zeros.
Anyways, I welcome comments on my code. Here is my code:
#include <stdio.h>
char res[100000];
int main() {
int n,i,j,m;
long temp,c;
while(scanf("%d",&n)!=EOF)
{
m=1;
res[0]=‘1’;
for(i=2;i<=n;i++){
c=0;
for(j=0;j<m;j++){
temp=((res[j]-48)*i)+c;
res[j]=(temp%10)+48;
c=temp/10;
}
while(c>0)
{
res[m]=(c%10)+48;
c=c/10;
m++;
}
}
for(i=m-1;i>=0;i–)
printf("%c",res[i]);
printf("\n");
}
return 0;
}
Please do suggest how to improve this code…!!
omg, this is really helpful. Thank you.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BigMultiplier
{
class Program
{
static void Main(string[] args)
{
int[] s1 = new int[1];
int[] s2 = new int[1];
s1[0]=1;
Program p = new Program();
int[] s3 = p.doit(s1, s2);
Console.WriteLine("Enter the Number for Which Factorial to be Found (below 1000)");
int limit = Convert.ToInt32(Console.ReadLine());
for (int i = 1; i <= limit; i++)
{
s3 = p.return_array(i);
s1 = p.doit(s1, s3);
}
int sum = 0;
for (int j = s1.Length-1; j >=0; j--)
{
Console.Write(s1[j]);
sum = sum + s1[j];
}
Console.Write("sum = "+sum);
Console.WriteLine();
Console.ReadLine();
}
int[] return_array(int num)
{
int[] num_arr = new int[1]; ;
if (num <= 9)
{
num_arr = new int[1];
num_arr[0] = num;
}
else if (num <= 99)
{
num_arr = new int[2];
num_arr[1] = num % 10;
num = num / 10;
num_arr[0] = num;
}
else if (num <= 999)
{
num_arr = new int[3];
num_arr[2] = num % 10;
num = num / 10;
num_arr[1] = num % 10;
num = num / 10;
num_arr[0] = num % 10;
}
else if (num <= 9999)
{
num_arr = new int[4];
num_arr[3] = num % 10;
num = num / 10;
num_arr[2] = num % 10;
num = num / 10;
num_arr[1] = num % 10;
num = num / 10;
num_arr[0] = num % 10;
}
else if (num <= 99999)
{
num_arr = new int[5];
num_arr[4] = num % 10;
num = num / 10;
num_arr[3] = num % 10;
num = num / 10;
num_arr[2] = num % 10;
num = num / 10;
num_arr[1] = num % 10;
num = num / 10;
num_arr[0] = num % 10;
}
return num_arr;
}
int[] doit(int[] num1_int, int[] num2_int)
{
// String num1_string, num2_string;
// Console.WriteLine(“Enter the Number 1”);
// num1_string = Console.ReadLine();
// Console.WriteLine(“Enter the Number 2”);
// num2_string = Console.ReadLine();
// int[] num1_int = new int[num1_string.Length];
// int[] num2_int = new int[num2_string.Length];
// for (int j = 0; j < num1_string.Length; j++)
// {
// num1_int[j] = num1_string[j]-48;
// Console.Write(" " + num1_int[j]);
// }
// for(int j=0;j<num2_string.Length;j++)
// {
// num2_int[j] = num2_string[j]-48;
// Console.Write(" " + num2_int[j]);
// }
int[,] num3_int = new int[num2_int.Length, (num1_int.Length + 1)];
int i,k,temp=0;
//Multiplication on Individual Digits Done and the Values are there in the Individual Cells of the Array
for(i=0;i<num2_int.Length;i++)
{
for (k = 0; k < num1_int.Length; k++)
{
int mul = (num1_int[k] * num2_int[i])+temp;
num3_int[i, k] = mul % 10;
temp = mul / 10;
if (k == (num1_int.Length - 1))
{
num3_int[i, k+1] = temp;
}
// Console.Write(" " + num3_int[i, k]);
}
// Console.Write(" " + num3_int[i, k]);
temp=0;
// Console.WriteLine();
}
// temp = 0;
// Console.ReadLine();
int[] result_int = new int[num1_int.Length + num2_int.Length];
// int[,] num3_int = new int[num2_string.Length, (num1_string.Length + 1)];
double result=0;
for(i=0;i<num2_int.Length;i++)
for (k = 0; k < (num1_int.Length + 1); k++)
{
// Console.Write(" i = " + i + " k=" + k+" “);
// Console.Write(num3_int[i, k]);
result=result+(num3_int[i,k]*Math.Pow(10,k)*Math.Pow(10,i));
// Console.WriteLine(” "+(num3_int[i,k]*Math.Pow(10,k)*Math.Pow(10,i)));
// Console.WriteLine("10^k " + Math.Pow(10,k));
}
int[,] num4_int= new int[num2_int.Length,num1_int.Length + num2_int.Length];
for (i = 0; i < num2_int.Length; i++)
{
for (k = 0; k < (num1_int.Length + 1); k++)
{
//for (int l = 0; l < 0; l++)
{
num4_int[i,k + i] = num3_int[i,k];
}
}
}
for (i = 0; i < num2_int.Length; i++)
{
for (k = 0; k < (num1_int.Length + num2_int.Length); k++)
{
// Console.Write(" " + num4_int[i, k]);
}
// Console.WriteLine();
}
int[] re_int = new int[num1_int.Length + num2_int.Length];
temp=0;
for (i = 0; i < re_int.Length; i++)
{
re_int[i] = 0;
for (k = 0; k < num2_int.Length; k++)
{
re_int[i] = num4_int[k, i] + re_int[i];
}
int t = re_int[i] + temp;
re_int[i]=t%10;
temp=t/10;
if(i==(re_int.Length-1))
{
//Need to check
}
}
// Console.WriteLine("Final Result - Reversed Order “);
// for(i=0;i<re_int.Length;i++)
// Console.Write(” "+re_int[i]);
// re_int[i+k]=;
// Console.WriteLine("Final Result - Correct Order “);
// for(i=re_int.Length-1;i>=0;i–)
// Console.Write(” " + re_int[i]);
// Console.WriteLine(result);
// Console.ReadLine();
return re_int;
}
}
}
ok thats a good idea
Thanks a lot 
I was always confused to do this task. And finally your post removed my confusion.
Thank you for your effective article.
#include<stdio.h>
#include<stdlib.h>
#define m double
m fact(m n)
{
m i,ans=1;
for(i=2;i<=n;i++)
ans=ans*i;
return ans;
}
int main()
{
m t,n;
int i;
scanf("%lf",&t);
n=(m)malloc(sizeof(m)*t);
for(i=0;i<t;i++)
scanf("%lf",&n[i]);
for(i=0;i<t;i++)
printf("\n%0.0lf",fact(n[i]));
return 0;
}
getting correct on compiler but gives wrong answer on codechef
The efficient way to calculate factorial is by calculating k-th last element on k-th iteration. If you can output to a file all you need is O(n) space lesser multiplications. infact, we can do that without multiplications.
Checkout for full article: