Computing sum of digits of large factorial

what is the efficient way to compute sum of digits of large factorial say 2000!?
I thought of using array to store the factorial and adding it, but is there any other efficient way out with out calculating factorial?

2 Likes

An array, where each index of the array stores a digit of the factorial would work. In case there are numerous queries and a small value of “N” (for which you need N!), use precomputation.

This tutorial might help.

1 Like

Bellow is the simple logic for computing factorial

#include< iostream>

#include< conio.h>

using namespace std;

void main()

{

int i,f=1,n;

    scanf("%d",&n);

for(i=1;i<=n;i++)

{

	f*=i;

}

printf("%d\n",f);


getch();

}
Now lets say that the factorial is stored in a variable n. To find out the sum of the digits of the value in the variable n, you can use the following logic given below accordingly.

#include< iostream>

#include< conio.h>

using namespace std;

int main()

{

int n,i,rev=0;

scanf("%d",&n);

for(i=0;n%10>0;i++)

{

	rev+=((n%10));



}

printf("%d",rev);

getch();

return 0;

}

@namankumar
Your code works fine with numbers upto 20,above that this logic fails.You’ll need to store it in an array.As 100 factorial contains 158 digits,very large even long long int.
You will find the right procedure below:-
http://discuss.codechef.com/questions/7349/computing-factorials-of-a-huge-number-in-cc-a-tutorial

Use python,

Since Python has big num data types also inbuilt functions it is very easy to compute sum of digits in factorial of n,
In this eample n = 2000

Here is a sample code

from math import factorial

#Store factorial of 2000 in a variable a
a=factorial(2000)

#Typecast variable to string
a=str(a)

#print a

#initialize a counter variable to add all numbers, to 0
add=0

#Iterate through the string a, i.e. factorial of 2000
for i in a:
    #Add each value after typecasting character into integer
    add+=int(i)

#Print sum of digits in factorial(2000)
print add
And thats it..!!

the number of digits in a number can be calculated as (floor(log10(x)))+1 or ceil(log10(x)) … where x is the number so
if factorial(x) can be calculated as follows - x! = x*(x-1) (x-2) … 1
so #digits in x! = ceil(log10(x!))
= ceil(log10(x
(x-1) *(x-2) … 1))
= ceil(log10(x) + log10(x-1)… +log10(1))

this is very simple and efficient to implement even for higher factorials
happy coding

1 Like