Contar dígitos en un factorial | Serie 1

Dado un entero n, 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

Una solución ingenua sería calcular la n! primero y luego calcular el número de dígitos presentes en él. Sin embargo, como el valor de n! puede ser muy grande, sería engorroso almacenarlos en una variable (¡a menos que esté trabajando en python!). 
Una mejor solución sería usar la propiedad útil de los logaritmos para calcular la respuesta requerida. 
 

We know,
log(a*b) = log(a) + log(b)

Therefore
log( n! ) = log(1*2*3....... * n) 
          = log(1) + log(2) + ........ +log(n)

Now, observe that the floor value of log base 
10 increased by 1, of any number, gives the
number of digits present in that number.

Hence, output would be : floor(log(n!)) + 1.

A continuación se muestra la implementación del mismo. 
 

// A C++ program to find the number of digits in
// a factorial
#include <bits/stdc++.h>
using namespace std;
 
// This function receives an integer n, and returns
// the number of digits present in n!
int findDigits(int n)
{
    // factorial exists only for n>=0
    if (n < 0)
        return 0;
 
    // base case
    if (n <= 1)
        return 1;
 
    // else iterate through n and calculate the
    // value
    double digits = 0;
    for (int i=2; i<=n; i++)
        digits += log10(i);
 
    return floor(digits) + 1;
}
 
// Driver code
int main()
{
    cout << findDigits(1) << endl;
    cout << findDigits(5) << endl;
    cout << findDigits(10) << endl;
    cout << findDigits(120) << endl;
    return 0;
}

// Java program to find the number
// of digits in a factorial
 
import java.io.*;
import java.util.*;
 
class GFG
{
    // returns the number of digits
    // present in n!
    static int findDigits(int n)
    {
        // factorial exists only for n>=0
        if (n < 0)
            return 0;
  
        // base case
        if (n <= 1)
            return 1;
  
        // else iterate through n and calculate the
        // value
        double digits = 0;
        for (int i=2; i<=n; i++)
            digits += Math.log10(i);
  
        return (int)(Math.floor(digits)) + 1;
    }
     
    // Driver code
    public static void main (String[] args)
    {
        System.out.println(findDigits(1));
        System.out.println(findDigits(5));
        System.out.println(findDigits(10));
        System.out.println(findDigits(120));
    }
}
 
// This code is contributed by Pramod Kumar

# Python3 program to find the
# number of digits in a factorial
import math
 
# This function receives an integer
# n, and returns the number of
# digits present in n!
 
def findDigits(n):
     
    # factorial exists only for n>=0
    if (n < 0):
        return 0;
 
    # base case
    if (n <= 1):
        return 1;
 
    # else iterate through n and
    # calculate the value
    digits = 0;
    for i in range(2, n + 1):
        digits += math.log10(i);
 
    return math.floor(digits) + 1;
 
# Driver code
print(findDigits(1));
print(findDigits(5));
print(findDigits(10));
print(findDigits(120));
 
# This code is contributed by mits

// A C++ program to find the number
// of digits in a factorial
using System;
 
class GFG {
     
    // This function receives an integer
    // n, and returns the number of
    // digits present in n!
    static int findDigits(int n)
    {
         
        // factorial exists only for n>=0
        if (n < 0)
            return 0;
     
        // base case
        if (n <= 1)
            return 1;
     
        // else iterate through n and
        // calculate the value
        double digits = 0;
        for (int i = 2; i <= n; i++)
            digits += Math.Log10(i);
     
        return (int)Math.Floor(digits) + 1;
    }
     
    // Driver code
    public static void Main()
    {
        Console.Write(findDigits(1) + "\n");
        Console.Write(findDigits(5) + "\n");
        Console.Write(findDigits(10) + "\n");
        Console.Write(findDigits(120) + "\n");
    }
}
 
// This code is contributed by
// Smitha Dinesh Semwal

<?php
// PHP program to find
// the number of digits
// in a factorial
 
// This function receives
// an integer n, and returns
// the number of digits present in n!
 
function findDigits($n)
{
    // factorial exists only for n>=0
    if ($n < 0)
        return 0;
 
    // base case
    if ($n <= 1)
        return 1;
 
    // else iterate through n and
    // calculate the value
    $digits = 0;
    for ($i = 2; $i <= $n; $i++)
        $digits += log10($i);
 
    return floor($digits) + 1;
}
 
// Driver code
echo findDigits(1), "\n";
echo findDigits(5), "\n";
echo findDigits(10), "\n";
echo findDigits(120), "\n";
 
// This code is contributed by Ajit.
?>

<script>
 
// A Javascript program to find the number of digits in
// a factorial
 
 
// This function receives an integer n, and returns
// the number of digits present in n!
function findDigits(n)
{
    // factorial exists only for n>=0
    if (n < 0)
        return 0;
 
    // base case
    if (n <= 1)
        return 1;
 
    // else iterate through n and calculate the
    // value
    let digits = 0;
    for (let i=2; i<=n; i++)
        digits += Math.log10(i);
 
    return Math.floor(digits) + 1;
}
 
// Driver code
  
    document.write(findDigits(1) + "<br>");
    document.write(findDigits(5) + "<br>");
    document.write(findDigits(10) + "<br>");
    document.write(findDigits(120) + "<br>");
     
 
//This code is contributed by Mayank Tyagi
 
</script>

Producción : 

1
3
7
199

Complejidad de tiempo: O (nlogn) desde que se calculó el registro en un bucle

En el siguiente conjunto, veríamos cómo optimizar aún más nuestro enfoque y reducir la complejidad del tiempo para el mismo programa. Ashutosh Kumar
contribuye con este artículo . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su 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.