Tutorialspoint.dev

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.

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:

1
363233781
8565705523
199

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter