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 <bits/stdc++.h> 
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

<?php 
// A optimised PHP program to find the  
// number of digits in a factorial 
  
// Returns the number of digits present  
// in n! Since the result can be large 
// long long is used as return type 
function 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 * log10($n / M_E) +  
                log10(2 * M_PI * $n) / 
                2.0)); 
  
    return floor($x) + 1; 
} 
  
    // Driver Code 
    echo findDigits(1)."
" ; 
    echo findDigits(50000000)."
" ; 
    echo findDigits(1000000000)."
" ; 
    echo findDigits(120) ; 
      
// This code is contributed by nitin mittal 
?> 

Output:

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Count digits in a factorial | Set 2

C++

Java

Python3

C#

PHP

tags:

You Might Also Like

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books