Contar dígitos en un factorial | conjunto 2

Dado un entero n (puede ser muy grande), encuentre el número de dígitos que aparecen en su factorial, donde factorial se define como, factorial(n) = 1*2*3*4……..*n y factorial(0 ) = 1
Ejemplos: 
 

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

Ya hemos discutido la solución para valores pequeños de n en Count dígitos en un factorial | conjunto 1 . Sin embargo, esa solución no sería capaz de manejar casos en los que n > 10^6 
Entonces, ¿podemos mejorar nuestra solución? 
Sí ! podemos. 
¡Podemos usar la fórmula de Kamenetsky para encontrar nuestra respuesta! 
 

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 

Y eso es ! 
Nuestra solución puede manejar entradas muy grandes que se pueden acomodar en un número entero de 32 bits, ¡ 
e incluso más! . 
A continuación se muestra la implementación de la idea anterior:
 

// 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;
}

// 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.

# 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

// 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
// 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)."\n" ;
    echo findDigits(50000000)."\n" ;
    echo findDigits(1000000000)."\n" ;
    echo findDigits(120) ;
     
// This code is contributed by nitin mittal
?>

<script>
 
// A optimised Javascript 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
    let x = ((n * Math.log10(n / Math.E) +
                Math.log10(2 * Math.PI * n) /
                2.0));
 
    return Math.floor(x) + 1;
}
 
// Driver Code
  
    document.write(findDigits(1) + "<br>");
    document.write(findDigits(50000000) + "<br>");
    document.write(findDigits(1000000000) + "<br>");
    document.write(findDigits(120) + "<br>");
 
// This code is contributed by Mayank Tyagi
 
</script>

Producción: 

1
363233781
8565705523
199

Método:  Primero encontrar el factorial de un número usando la función factorial y luego usando el bucle while para encontrar el número de dígitos presentes en el número factorial.
 

# Python code to count number of digits
# in a factorial of a number
 
# importing math module
from math import*
n=10;c=0
# finding factorial of a number
f=factorial(n)
# counting the number of digits present
# in the factoral number
while(f!=0):
  f//=10
  c+=1
print(c)
 
 
# this code is contributed by gangarajula laxmi

<script>
       // JavaScript code for the above approach
       function factorial(n) {
           let fact = 1;
           for (let i = 1; i <= n; i++) {
               fact = fact * i;
           }
           return fact;
       }
       let n = 10; c = 0
       // finding factorial of a number
       let f = factorial(n)
       // counting the number of digits present
       // in the factoral number
       while (f != 0) {
           f = Math.floor(f / 10)
           c += 1
       }
       document.write(c);
   // This code is contributed by Potta Lokesh
   </script>

7

Referencias: oeis.org 
Este artículo es una contribución de Ashutosh Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.