Contar ceros finales en factorial de un número

Dado un entero n, escriba una función que devuelva el recuento de ceros finales en n!. 
Ejemplos: 

Input: n = 5
Output: 1 
Factorial of 5 is 120 which has one trailing 0.

Input: n = 20
Output: 4
Factorial of 20 is 2432902008176640000 which has
4 trailing zeroes.

Input: n = 100
Output: 24

Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.

1. Enfoque:
   un método simple es calcular primero el factorial de n, luego contar los ceros finales en el resultado (podemos contar los ceros finales dividiendo repetidamente el factorial por 10 hasta que el resto sea 0).
    
2. El método anterior puede causar un desbordamiento para números ligeramente más grandes, ya que el factorial de un número es un número grande (consulte el factorial de 20 dado en los ejemplos anteriores). La idea es considerar factores primos de un factorial n. Los factores primos 2 y 5 siempre producen un cero final. Si podemos contar el número de 5 y 2, nuestra tarea está hecha. Considere los siguientes ejemplos.
   n = 5: ¡Hay un 5 y 3 2 en factores primos de 5! (2*2*2*3*5). Por lo tanto, la cuenta de 0 finales es 1.
   n = 11: ¡Hay dos 5 y ocho 2 en factores primos de 11! (2 ⁸ * 3 ⁴ * 5 ² * 7). Entonces, el conteo de 0 finales es 2.
    
3. Podemos observar fácilmente que el número de 2 en factores primos siempre es mayor o igual que el número de 5. Así que si contamos 5s en factores primos, hemos terminado. ¿Cómo contar el número total de 5s en factores primos de n!? Una forma sencilla es calcular el suelo (n/5). Por ejemplo, ¡7! tiene un 5, 10! tiene dos 5s. Todavía no está hecho, hay una cosa más a considerar. Números como el 25, 125, etc tienen más de un 5. Por ejemplo, si consideramos el 28! obtenemos un 5 adicional y el número de 0 se convierte en 6. El manejo de esto es simple, primero, divida n entre 5 y elimine todos los 5 individuales, luego divida entre 25 para eliminar los 5 adicionales, y así sucesivamente. A continuación se muestra la fórmula resumida para contar los ceros finales.

Trailing 0s in n! = Count of 5s in prime factors of n!
                  = floor(n/5) + floor(n/25) + floor(n/125) + ....

El siguiente es un programa basado en la fórmula anterior: 

// C++ program to count
// trailing 0s in n!
#include <iostream>
using namespace std;
 
// Function to return trailing
// 0s in factorial of n
int findTrailingZeros(int n)
{
    if (n < 0) // Negative Number Edge Case
        return -1;
 
    // Initialize result
    int count = 0;
 
    // Keep dividing n by powers of
    // 5 and update count
    for (int i = 5; n / i >= 1; i *= 5)
        count += n / i;
 
    return count;
}
 
// Driver Code
int main()
{
    int n = 100;
    cout << "Count of trailing 0s in " << 100 << "! is "
         << findTrailingZeros(n);
    return 0;
}

// Java program to count
// trailing 0s in n!
import java.io.*;
 
class GFG {
    // Function to return trailing
    // 0s in factorial of n
    static int findTrailingZeros(int n)
    {
        if (n < 0) // Negative Number Edge Case
            return -1;
 
        // Initialize result
        int count = 0;
 
        // Keep dividing n by powers
        // of 5 and update count
        for (int i = 5; n / i >= 1; i *= 5)
            count += n / i;
 
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 100;
        System.out.println("Count of trailing 0s in " + n
                           + "! is "
                           + findTrailingZeros(n));
    }
}
 
// This code is contributed by Pramod Kumar

# Python3 program to
# count trailing 0s
# in n!
 
# Function to return
# trailing 0s in
# factorial of n
 
 
def findTrailingZeros(n):
    # Negative Number Edge Case
    if(n < 0):
        return -1
 
    # Initialize result
    count = 0
 
    # Keep dividing n by
    # 5 & update Count
    while(n >= 5):
        n //= 5
        count += n
 
    return count
 
 
# Driver program
n = 100
print("Count of trailing 0s " +
      "in 100! is", findTrailingZeros(n))
 
# This code is contributed by Uttam Singh

// C# program to count
// trailing 0s in n!
using System;
 
class GFG
{
     
    // Function to return trailing
    // 0s in factorial of n
    static int findTrailingZeros(int n)
    {
       
          if(n < 0) //Negative Number Edge Case
              return -1;       
       
        // Initialize result
        int count = 0;
 
        // Keep dividing n by powers
        // of 5 and update count
        for (int i = 5; n / i >= 1; i *= 5)
            count += n / i;
 
        return count;
    }
     
    // Driver Code
    public static void Main ()
    {
        int n = 100;
        Console.WriteLine("Count of trailing 0s in " +
                                           n +"! is "+
                                findTrailingZeros(n));
    }
}
 
// This code is contributed by vt_m

<?php
// PHP program to count
// trailing 0s in n!
 
// Function to return trailing
// 0s in factorial of n
function findTrailingZeros( $n)
{
   
      if($n < 0) //Negative Number Edge Case
      return -1;   
   
    // Initialize result
    $count = 0;
 
    // Keep dividing n by powers
    // of 5 and update count
    for ($i = 5; $n / $i >= 1; $i *= 5)
        $count += $n / $i;
 
    return $count;
}
 
// Driver Code
 
$n = 100;
echo "Count of trailing 0s in " , 100,
     "! is " , findTrailingZeros($n);
 
// This code is contributed by vt_m
?>

<script>
 
// JavaScript program to count
// trailing 0s in n!
 
// Function to return trailing
// 0s in factorial of n
function findTrailingZeros(n)
{
 
    if(n < 0) //Negative Number Edge Case
      return -1;
     
    // Initialize result
    let count = 0;
 
    // Keep dividing n by powers of
    // 5 and update count
    for (let i = 5; Math.floor(n / i) >= 1; i *= 5)
        count += Math.floor(n / i);
 
    return count;
}
 
// Driver Code
    let n = 100;
    document.write("Count of trailing 0s in " + 100
        + "! is " + findTrailingZeros(n));
 
// This code is contributed by Surbhi Tyagi
 
</script>

Producción : 

Count of trailing 0s in 100! is 24 

Complejidad de tiempo: O (log ₅ n)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Rahul Jain . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.