# Count digits in a factorial | Set 2

Given an integer n (can be very large), find the number of digits that appear in its factorial, where factorial is defined as, factorial(n) = 1*2*3*4……..*n and factorial(0) = 1

Examples:

```Input :  n = 1
Output : 1
1! = 1, hence number of digits is 1

Input :  5
Output : 3
5! = 120, i.e., 3 digits

Input : 10
Output : 7
10! = 3628800, i.e., 7 digits

Input : 50000000
Output : 363233781

Input : 1000000000
Output : 8565705523
```

We’ve already discussed the solution for small values of n in the Count digits in a factorial | Set 1. However that solution would not be able to handle cases where n >10^6
So, can we improve our solution ?
Yes ! we can.
We can use Kamenetsky’s formula to find our answer !

```It approximates the number of digits in a factorial by :
f(x) =    log10( ((n/e)^n) * sqrt(2*pi*n))

Thus, we can pretty easily use the property of logarithms to,
f(x) = n* log10(( n/ e)) + log10(2*pi*n)/2

```

And that’s it !
Our solution can handle very large inputs that can be accommodated in a 32 bit integer,
and even beyond that ! .
Below is the implementation of above idea :

## C++

 `// A optimised program to find the  ` `// number of digits in a factorial ` `#include ` `using` `namespace` `std; ` ` `  `// Returns the number of digits present  ` `// in n! Since the result can be large ` `// long long is used as return type ` `long` `long` `findDigits(``int` `n) ` `{ ` `    ``// factorial of -ve number  ` `    ``// doesn't exists ` `    ``if` `(n < 0) ` `        ``return` `0; ` ` `  `    ``// base case ` `    ``if` `(n <= 1) ` `        ``return` `1; ` ` `  `    ``// Use Kamenetsky formula to calculate ` `    ``// the number of digits ` `    ``double` `x = ((n * ``log10``(n / M_E) +  ` `                 ``log10``(2 * M_PI * n) / ` `                 ``2.0)); ` ` `  `    ``return` `floor``(x) + 1; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``cout << findDigits(1) << endl; ` `    ``cout << findDigits(50000000) << endl; ` `    ``cout << findDigits(1000000000) << endl; ` `    ``cout << findDigits(120) << endl; ` `    ``return` `0; ` `} `

## Java

 `// An optimised java program to find the ` `// number of digits in a factorial ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG { ` `    ``public` `static` `double` `M_E = ``2.71828182845904523536``; ` `    ``public` `static` `double` `M_PI = ``3.141592654``; ` ` `  `     ``// Function returns the number of ` `     ``// digits present in n! since the ` `     ``// result can be large, long long  ` `     ``// is used as return type ` `    ``static` `long` `findDigits(``int` `n) ` `    ``{ ` `        ``// factorial of -ve number doesn't exists ` `        ``if` `(n < ``0``) ` `            ``return` `0``; ` ` `  `        ``// base case ` `        ``if` `(n <= ``1``) ` `            ``return` `1``; ` ` `  `        ``// Use Kamenetsky formula to calculate ` `        ``// the number of digits ` `        ``double` `x = (n * Math.log10(n / M_E) + ` `                    ``Math.log10(``2` `* M_PI * n) /  ` `                    ``2.0``); ` ` `  `        ``return` `(``long``)Math.floor(x) + ``1``; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``System.out.println(findDigits(``1``)); ` `        ``System.out.println(findDigits(``50000000``)); ` `        ``System.out.println(findDigits(``1000000000``)); ` `        ``System.out.println(findDigits(``120``)); ` `    ``} ` `} ` ` `  `// This code is contributed by Pramod Kumar. `

/div>

## Python3

 `# A optimised Python3 program to find  ` `# the number of digits in a factorial ` `import` `math ` ` `  `# Returns the number of digits present  ` `# in n! Since the result can be large ` `# long long is used as return type ` `def` `findDigits(n): ` `     `  `    ``# factorial of -ve number  ` `    ``# doesn't exists ` `    ``if` `(n < ``0``): ` `        ``return` `0``; ` ` `  `    ``# base case ` `    ``if` `(n <``=` `1``): ` `        ``return` `1``; ` ` `  `    ``# Use Kamenetsky formula to ` `    ``# calculate the number of digits ` `    ``x ``=` `((n ``*` `math.log10(n ``/` `math.e) ``+`  `              ``math.log10(``2` `*` `math.pi ``*` `n) ``/``2.0``)); ` ` `  `    ``return` `math.floor(x) ``+` `1``; ` ` `  `# Driver Code ` `print``(findDigits(``1``)); ` `print``(findDigits(``50000000``)); ` `print``(findDigits(``1000000000``)); ` `print``(findDigits(``120``)); ` `     `  `# This code is contributed by mits `

## C#

 `// An optimised C# program to find the ` `// number of digits in a factorial. ` `using` `System; ` ` `  `class` `GFG { ` `    ``public` `static` `double` `M_E = 2.71828182845904523536; ` `    ``public` `static` `double` `M_PI = 3.141592654; ` ` `  `    ``// Function returns the number of ` `    ``// digits present in n! since the ` `    ``// result can be large, long long  ` `    ``// is used as return type ` `    ``static` `long` `findDigits(``int` `n) ` `    ``{ ` `        ``// factorial of -ve number  ` `        ``// doesn't exists ` `        ``if` `(n < 0) ` `            ``return` `0; ` ` `  `        ``// base case ` `        ``if` `(n <= 1) ` `            ``return` `1; ` ` `  `        ``// Use Kamenetsky formula to calculate ` `        ``// the number of digits ` `        ``double` `x = (n * Math.Log10(n / M_E) +  ` `                    ``Math.Log10(2 * M_PI * n) /  ` `                    ``2.0); ` ` `  `        ``return` `(``long``)Math.Floor(x) + 1; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``Console.WriteLine(findDigits(1)); ` `        ``Console.WriteLine(findDigits(50000000)); ` `        ``Console.WriteLine(findDigits(1000000000)); ` `        ``Console.Write(findDigits(120)); ` `    ``} ` `} ` ` `  `// This code is contributed by Nitin Mittal `

## PHP

 ` `

Output:

```1
363233781
8565705523
199
```