Write a program that takes input between 1 and 100 and finds its factorial.
Solution
Often students find this problem as assignment or algorithm exercise. Some of them even get fed up and skip this problem because you have to make calculations on large numbers. We all know that C++ 32 bit unsigned integer can hold data up to 4294967295 and long long i.e. 64 bit integer can handle at max 264 - 1 = 18446744073709551615. What do you think what is the maximum value whose factorial can be saved in 64 bit int. You can't even store 25's factorial in it as 25! = 15511210043330985984000000 :)
In this post, I will explain how easy it is to actually implement this algorithm. In the second part of this post, we will optimize our algorithm and will reduce some calculations.
Let us start!
First thing we have to keep in mind that we actually need a function that has the capability to multiply fairly large numbers.
We multiply two numbers usually by multiplying each digit of first number with each digit of 2nd number. For example if I have to multiply 123 to 1234:
- I will actually find 3 x 1234 = 3702, 2 x 1234 = 2468 and 1 x 1234 = 1234.
- I also have to add some zeros on the right side as I move from right to left.
- And then I will add all these values i.e. 3702 + 24680 + 123400 = 151782.
Voila!!! you noted something, we have to implement another function that can add two large numbers. Don't worry, it is good that we have found it initially. Let us assume that we already have a function that can add two numbers 'string add(string str1, string str2)' Now the function mul is quite simple to write that will multiply two very large numbers.
string mul(string str1, string str2)
{
string ans;
for(int i = str1.size()-1; i>=0; i--)
{
string sum;
int carry = 0;
//Step 1. above
for(int j = str2.size()-1; j >=0; j--)
{
//multiply two digits and add carry
int k = ((str1[i]-'0')*(str2[j]-'0') + carry);
sum = (char)((k % 10) + '0') + sum;
carry = (k/10);
}
if(carry > 0)
{
sum = (char)(carry+'0') + sum;
}
//Step 2. above
for(int j = 0; j < str1.size() - 1 - i; j++)
{
sum+="0";
}
//Step 3. above
ans = add(ans, sum);
}
return ans;
}
And here we go with the add function, I think it is pretty simple to understand
string add(string str1, string str2)
{
int n1 = str1.size(), n2 = str2.size();
for(int i = 0; i < n1 - n2; i++) //Make 134 as 00134 if 2nd number is 12345
str2 = "0" + str2;
for(int i = 0; i < n2 - n1; i++)
str1 = "0" + str1;
string ans;
int carry = 0;
for(int i = str1.size() - 1; i >= 0; i--)
{
ans = (char)((str1[i] - '0' + str2[i] - '0' + carry) % 10 + '0') + ans;
carry = (str1[i] - '0' + str2[i] - '0' + carry)/10;
}
if(carry > 0)
ans = (char)(carry + '0') + ans;
return ans;
}
Now what is more difficult for you. Here comes the Factorial function:
int N = 25; //We need 25!
string ans = 1;
for(j = 1; j <= N; j++)
{
stringstream ss;
ss << j;
ans = mul(ss.str(),ans);
}
Optimization
Just check one important thing, even we have to multiply small numbers. we have to make large calculations.
For example, if I want to multiply 10000 to 9999. I have to make 20 calculations but it is possible in just 1 calculation and the result can also be saved in an integer so we can optimize our algorithm in this way.
We will not call mul( ) function, until and unless it exceeds the limit of an integer that is '2147483647' and then multiply it with the next number.
25! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22 x 23 x 24 x 25
Now we can find product upto 12 i.e. '479001600' and from 13 to 19 i.e. '253955520' and then call mul( ) function on these two strings.I am sure, it will save a lot of calculations.
