## Tutorial for Small Factorials |

Hello all !

The problem that we will be taking up is http://www.codechef.com/problems/FCTRL2/ :)

This problem basically asks you to calculate the factorial of a number up to 100. Now, I guess most of you know what a "factorial" is. For those who don't, the factorial of a number N is 1*2*...*N. This problem would be very simple, had it not been for the maximum value of N. The structure of the problem is such that it asks the user to take the number of test cases as the first input. Then 't' integers follow where 't' is the number of test cases which was given as input previously.

For every integer here, we have to calculate the factorial. This is very simple in languages like python or java which have built-in support for big integer types. It proves to be a hassle for people using C / C++ or languages that do not have a built-in biginteger type. Let's think about how we can store the the result.

Now, the maximum number that we can store in an unsigned 32 bit integer is 2 ^ 32 - 1 and in an unsigned 64 bit integer is 2 ^ 64 - 1. Something like 100!('!' is the notation for factorial) has over 150 decimal digits. The data types mentioned earlier can store numbers having at most 9 and 19 decimal digits respectively. So, we need to find a way to store the 150+ digits that we will get as the answer. The simplest data structure that we can use is an integer array of size of about 200 to be on the safe side.

In the simplest form, let us store one decimal digit per array index. So, if the number is say 120, then the array will have the numbers as follows:

Say *a*[200] is how we declare the array, then

*a*[0] = 0

*a*[1] = 2

*a*[2] = 1

The least significant digit is stored in the lowest index 0. The next one in index 1 and so on. Along with the array, we need an integer specifying the total number of digits in the array at the given moment. Let this number be '*m*'. Initially, *a*[0] will be 1 and the value of '*m*' will be 1 specifying that we have just one digit in the array.

Let's take a simple example first. Consider that the array has some value like 45 and we need to multiply it with a value 37. This can be done in the following way.

**The array will be:**

*a*[0] = 5

*a*[1] = 4

and the value of *m* will be 2 specifying that there are 2 digits in the array currently.

Now, to multiply this array with the value 37. We start off from the index 0 of the array to index 1. At every iteration, we calculate 37 * *a*[index]. We also maintain a temporary variable called *temp* which is initialized to 0. Now, at every step, we calculate *x = a[index] * 37 + temp*. The new value of *a*[index] will be *x* % 10 and the new value of *temp* will be *temp / 10*. We are simply carrying out multiplication the way it is carried out usually. So, for the current situation, the iterations will be something like this.

Initialize *temp* = 0

**Iteration 1 : **

array = **(5, 4)**

temp = 0

index = 0, a[index] = 5

x = a[index] * 37 + temp = 5 * 37 + 0 = 185.

the new value of a[index] = 185 % 10 which is 5 and the new value of temp is 185 / 10 which is 18

**Iteration 2 :**

array : **(5, 4)**

temp = 18

index = 1, a[index] = 4

x = a[index] * 37 + temp = 4 * 37 + 18 = 166.

the new value of a[index] = 166 % 10 which is 6 and the new value of temp is 166 / 10 which is 16

We have finished 2 iterations and this is the value of '*m*', the array size at the moment. The required number of iterations is now over, but the value of *temp* is still greater than 0. This means that the current value of *temp* is to be incorporated into the array. For that, we keep appending the last digit of *temp* to the array and divide *temp* by 10 till *temp* becomes 0. So, we will get something like

**Iteration 1 : **

temp = 16 , array = **(5, 6)**

So, we add 16 % 10 to the array so that the array becomes** (5, 6, 6)** and we divide temp by 10 so that temp becomes 1. We update the value of 'm' to m + 1 that is m = 3

**Iteration 2 :**

temp = 1, array = **(5, 6, 6)**

Now, we add 1 % 10 to the array so the array becomes **(5, 6, 6, 1)** and we divide temp by 10 so that temp becomes 0. We update the value of 'm' to m + 1 that is m = 4

The value of *temp* is now 0 and our multiplication is now over. The final array we get is **(5, 6, 6, 1)**

Voila, we have the answer to 45 * 37 in our array with the Least significant digit in the 0th position. :)

For finding the factorial, we need to carry out this exact multiplication operation at every step as we loop from 1 to N. At the end of the Nth iteration, our array will contain

the answer and the value of m will be the number of digits in the answer. We can then just print the array from the Most significant digit to the least for the answer.

The basic flow of the program will be as below :

[code]

Start

Take in the number of test cases

While there is a test case remaining to be handled

Take in the number whose factorial is to be found, let it be N

Initialize the arrays 0th index to 1 and m to 1

Initialize i to 1

While i is less than or equal to N

Carry out multiplication of the array with 'i' as shown above.

Print the contents of the array starting from the most significant digit and ending with the least significant digit.

Stop

[/code]

Certain improvements can be made to the above mentioned method. We are storing only one digit per array index, We can store more than 1 digit per index so that the number of computations are reduced. The method to do that is the same as above. We leave it to the reader as an exercise :)

## Comments

**Please login at the top to post a comment.**

## If the number of test cases

hunnysingh@ 29 Nov 2009 11:21 PMIf the number of test cases is high, why dont we preprocess all the factorials and store them as char * and then as we get the input we just flush out the stored number. Such preprocessing will be useful when any test case value can be = N.

## Thanks , good tutorial .

magiix@ 30 Nov 2009 09:15 PMThanks , good tutorial .

## i need some sample

jeevi@ 1 Dec 2009 04:39 PMi need some sample programs..... pls

## great tutorial ty:):):)

maagi@ 4 Dec 2009 09:27 AMgreat tutorial ty:):):)

## wow! what a tutorial!! it

jagadish1989@ 20 Dec 2009 06:41 AMwow! what a tutorial!! it enlightened me a lot thanks a tonne admin :) :)

## thnx ! !

Geniusguy@ 30 Dec 2009 11:00 PMthnx ! !

## great

sahilsingla@ 11 Jan 2010 11:43 PMgreat tutorial.............:) it opened closed doors of my brain....

## That Really Helped!

Fahim Dalvi@ 12 Jan 2010 09:07 PMThat Really Helped!

## nice trick!

chandniverma@ 20 Jan 2010 08:39 AMnice trick!

## AN EXCELLENT ONE!! REALLY

letusc@ 27 Jan 2010 01:22 AMAN EXCELLENT ONE!! REALLY AWESOME

## GOOD TUTORIAL

enigmatickoder@ 27 Jan 2010 03:16 PMGOOD TUTORIAL## awesome, it teaches a simple

abhinavupadhya@ 31 Jan 2010 02:59 AMawesome, it teaches a simple and easy way to represent very large values in our C programs, this is very much appreciated!!

thanks :-)

## great tutorial

legendofseeker@ 3 Feb 2010 05:32 PMgreat tutorial

## #include<stdio.h>#include<str

magiix@ 9 Feb 2010 06:20 AM#include<stdio.h>

#include<string>

#include<string.h>

using namespace std;

char arr[200],res[200];

string table[150];

string multiply(string n,int m)

{

int N=n.size(),M=N,temp=0;

for(int i=0;i<N;i++)

arr[i]=n[N-1-i];

for(int i=0;i<N;i++)

{

int x=m*arr[i]+temp;

arr[i]=x%10;

temp=x/10;

}

while(temp>0)

{

arr[N]=temp%10;

temp/=10;

N++;

}

for(int i=0;i<M;i++)

res[i]=arr[M-1-i];

return res;

}

void make_table()

{

table[1]='1';

for(int i=2;i<101;i++)

{

table[i]=multiply(table[i-1],i);

}

}

int main()

{

int tc,n;

scanf(" %d",&tc);

make_table();

while(tc--)

{

scanf(" %d",&n);

printf("%sn",table[n]);

}

return 0;

}

can anyone help me fix my code ???

## I fixed it Thanks :D

magiix@ 10 Feb 2010 06:48 AMI fixed it Thanks :D

## even java doesn't give

shubh09@ 13 Feb 2010 03:18 PMeven java doesn't give correct answers if we try to compute factorials of nos. greater than 20 even after using the long data type. this trick really helps...

## Really helped me..tnx..

bharathgowri@ 27 Feb 2010 08:42 AMReally helped me..tnx..

## n1

dharmik@ 2 Mar 2010 06:28 AMn1

## why do use this "using

udit_rastogi@ 18 Mar 2010 03:32 PMwhy do use this

"using namespace std;"

i didn't study it in which compiler this is used.

i study c++ in 12 with sumita arora book..

so in which compiler i have to write the program

## Great tutorial! Thanks....

shashankl@ 26 Mar 2010 07:54 PMGreat tutorial! Thanks....

## Good Tutorial, Really

S-Harpreet@ 28 Mar 2010 06:50 PMGood Tutorial, Really helpful, thanx

## great man good use of data

tipsy25187@ 12 May 2010 07:08 PMgreat man good use of data stuructures

## trick is awesome!!

amartyaamp@ 8 Jun 2010 03:33 PMtrick is awesome!!

## @udit rastogi : we used turbo

DJ_rocks@ 13 Jun 2010 11:21 AM@udit rastogi : we used turbo C to program in class 12 from sumita arora. I'd recommend the same to you

## Awesome tutorial thanx Admin

DevilsEye@ 22 Jun 2010 12:38 PMAwesome tutorial thanx Admin for posting this it really helped...now we can compute any length of digit..:D

## @Admin :How did you get the

sloth@ 30 Jul 2010 11:23 PM@Admin :How did you get the LSB in lowest array index ?

## great tutorial!!!! really

aabidhasan@ 2 Aug 2010 09:57 AMgreat tutorial!!!! really helpful

## dat was truely informative!!!

ejoe@ 18 Sep 2010 08:02 AMdat was truely informative!!!

## awesome tutorial !!

naveenraiit@ 26 Sep 2010 05:59 PMawesome tutorial !!## its awesome

janardhan7@ 27 Sep 2010 05:52 PMits awesome

## Can someone show me the code?

knightyau@ 17 Oct 2010 08:13 PMCan someone show me the code? cant understand very well :(

## Please reply me need help :(

knightyau@ 17 Oct 2010 08:15 PMPlease reply me need help :( thanks in advanced.wanna learn this very desperately.

## i get it thanks ;)

knightyau@ 20 Oct 2010 09:48 PMi get it thanks ;)

## this frickin awesome!! <3

ankeetmaini@ 9 Nov 2010 06:19 PMthis frickin awesome!! <3

## nice tutorial ! really nice

rabba_alam@ 24 Nov 2010 07:17 AMnice tutorial ! really nice thanks !!!!

## Nice tutorial... :)

bithin2007@ 25 Nov 2010 06:18 PMNice tutorial... :)

## #include<iostream> using

kezzy@ 4 Jan 2011 08:29 PM#include<iostream>

using namespace std;

int main(void){

int t,m,i,p=0,k=0;

cin>>t;

int a[1000][1000];

while(t--){

long int x,n,r;

cin>>n;

a[p][0]=i=1;

r=n;

while(n){

a[p][m++]=n%10;

n/=10;

}

long int temp=0;

for(int j=r-1,i=0;j>0;j--,i++){

while(k==m){

x=a[p][i]*j+temp;

a[p][i]=x%10;

temp=x/10;

k++;

}

while(temp){

a[p][i++]=temp%10;

temp/=10;

}

}

p++;

}

for(k=0;k<=p;k++){

for(int j=i--;j>=0;j--){

cout<<a[k][j];

}

cout<<"n";

}

}

## GooD Tut

kooljay999@ 16 Feb 2011 02:59 AMGooD Tut

## great tutorial!!!! really

bsp23@ 4 Mar 2011 04:32 PMgreat tutorial!!!! really helpful

## great tutorial thanxxxxxx :)

Garry@ 21 Mar 2011 07:57 PMgreat tutorial thanxxxxxx :)

## awesome trick .. .thanx. .

ratz@ 31 Mar 2011 11:53 AMawesome trick .. .thanx. .

## ooooooooooooookkkkkkkkkkkkkkk

apudxtr@ 8 Apr 2011 03:31 PMooooooooooooookkkkkkkkkkkkkkkkkkkkkkk........thnx man.

## thanx a lot, great tutorial

princeofpersia@ 18 Apr 2011 01:57 PM## thanx a lot, great tutorial !

## Awesome tutorial

lordaragon@ 1 May 2011 07:49 PMAwesome tutorial

## hi i need a sample java

sampathmse@ 10 May 2011 11:24 AMhi i need a sample java program pls ....

## AWESOME,,,,,,SUPERB TUTE

hungrycoder@ 16 Jun 2011 07:58 PM## nice 1.. thanx

bootstrap@ 20 Jun 2011 10:55 PM## awsome one budy ...thanks a

gupta@ 15 Aug 2011 08:48 PM## Sorry for stupid questions

gennadz@ 14 Sep 2011 07:34 PM## thanx for the tutorial......

balabarath@ 21 Sep 2011 08:56 PM## thankz a ton..gr8 tut..

ritanjandawn@ 24 Sep 2011 02:50 PM## The following code runs

buzz92@ 30 Sep 2011 03:44 PM## awesome!!!

riseabove@ 1 Oct 2011 11:25 PM## Great tutorial! Thanks a lot

cinash@ 3 Oct 2011 07:18 AM## AWESOME!!!

sinha2011@ 4 Oct 2011 04:43 PM## java has BIGINTEGER type data

checklist@ 8 Oct 2011 02:17 PM## The only error I get is an

divyamrastogi@ 27 Nov 2011 04:00 PM## #include int main() {int

anshu1710@ 18 Dec 2011 04:28 PM## check it for nos greater than

goudam_jm@ 19 Dec 2011 02:53 PM## tanx :)))

tj91@ 29 Dec 2011 06:52 PM## its very nice

rky_rajkumar@ 29 Dec 2011 07:18 PM## #include int a[100]; void

sandeepsuraj7@ 11 Jan 2012 12:03 PM## A good tutorial, thanks admin

abhi31jeet@ 24 Feb 2012 11:25 PM## my algo is exactly same like

hellodear@ 10 Mar 2012 02:51 AM## @admin : I tried bitwise

mohyt@ 14 Mar 2012 08:39 PM## really nice explanation... so

sharatsn123@ 18 Mar 2012 08:20 PM## I remember i used same

jadaayu@ 21 Mar 2012 11:43 PM## Nice tutorial.....helped a

cool_techie@ 25 Mar 2012 10:26 AM## very very good tutorial it

vinod176singh@ 4 Apr 2012 05:51 PM## great tutorial tyu

neeraj6@ 14 Apr 2012 02:28 AM## you can use BIG INTEGER class

pointer@ 17 May 2012 05:07 PM## Thanks a lot... :-) good to

brinz1n2904@ 18 May 2012 01:29 PM## trying..

madvee@ 3 Jun 2012 04:18 PM## ahh exactly what was needed,

elva136@ 20 Sep 2012 10:17 AM## great tutorial!!! thanks

shweta_19@ 6 Oct 2012 07:39 PM## Great tutorial. Thank you

govind285@ 22 Dec 2012 01:17 AM## Thankyou for the tutorial,

nishad94@ 15 Jan 2013 09:17 AM## lots of thanks :)

callam2pm@ 1 Jun 2013 11:49 AM## thanx

nikhil_manit@ 6 Sep 2013 05:52 PM## in my program saying time

nikhil_manit@ 7 Sep 2013 07:40 PM## thanks a ton for such a nice

sunny73@ 16 Oct 2013 10:37 AM## Good tutorial.

aggrwll@ 17 Mar 2014 11:14 AM## table lookup methods won't

eightnoteight@ 16 May 2014 09:10 AM## thnx admin :)

venyush11_2@ 16 Jun 2014 11:01 AM## try 5*2 using above method

v4_adi@ 17 Jun 2014 02:17 AM## great tutorial it is

charit_88@ 27 Jun 2014 09:07 AM## awsum tutorial.....helped me

nameisyash@ 9 Jul 2014 12:28 AM## awesome lesson!

shubhamk647@ 11 Sep 2014 07:14 AM## great tutorial . thanx a lot

devildeepak1@ 29 Oct 2014 01:47 PM## great one

saisumit@ 15 Dec 2014 01:00 AM## thnx for this great tutorial

kaka_ind1995@ 20 Dec 2014 01:10 AM## I didn't understand.can

anjan55@ 22 Feb 2015 09:13 PM## I didn't understand.can

krish5_varam@ 25 Feb 2015 09:18 AM## Thanks you so much for a

hari_manikanta@ 6 Mar 2015 12:04 PM## Thanks for the awesome

aakash_729@ 20 May 2015 03:15 AM## Thanks for the awesome

nazmul129@ 22 May 2015 07:38 PM## Nice explanation, its very

amit_s95@ 25 May 2015 05:59 PM## thanks for sharing with us

nedved1000@ 30 Jun 2015 12:20 AM## Thanks for post this helpful

kskumar554@ 17 Jul 2015 04:57 PM## This article is really

kskumar554@ 17 Jul 2015 04:57 PM## Thanks for all your

kskumar554@ 17 Jul 2015 04:58 PM## This article is really

akashseo@ 22 Jul 2015 12:07 PM## Thanks for all your

akashseo@ 22 Jul 2015 12:08 PM## Thanks for all your

akashseo@ 22 Jul 2015 12:09 PM## This article is really

akashseo@ 22 Jul 2015 12:10 PM