Número de ceros finales en N * (N – 2) * (N – 4)*….

Dado un número entero N , la tarea es encontrar el número de ceros finales en la notación decimal de f(N) donde f(N) = 1 si N < 2 y f(N) = N * f(N – 2) si norte ≥ 2

Ejemplos:  

Entrada: N = 12 
Salida: 1 
f(12) = 12 * 10 * 8 * 6 * 4 * 2 = 46080

Entrada: N = 7 
Salida: 0 
 

Enfoque: el número de ceros finales cuando f(N) se expresa en notación decimal es el número de veces que f(N) es divisible por 2 y el número de veces que f(N) es divisible por 5 . Hay dos casos:  

1. Cuando N es impar, entonces f(N) es el producto de algunos números impares, por lo que no se rompe en 2 . Entonces la respuesta siempre es 0 .
2. Cuando N es par, entonces f(N) se puede representar como 2 (1 * 2 * 3 * …. * N/2) . El número de veces que f(N) es divisible por 2 es mayor que el número de veces que es divisible por 5 , así que solo considera el número de veces que es divisible por 5 . Ahora, este problema es similar a contar ceros finales en factorial de un número .

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// trailing 0s in the given function
int findTrailingZeros(int n)
{
    // If n is odd
    if (n & 1)
        return 0;
 
    // If n is even
    else {
        int ans = 0;
 
        // Find the trailing zeros
        // in n/2 factorial
        n /= 2;
        while (n) {
            ans += n / 5;
            n /= 5;
        }
 
        // Return the required answer
        return ans;
    }
}
 
// Driver code
int main()
{
    int n = 12;
 
    cout << findTrailingZeros(n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
    // Function to return the count of
    // trailing 0s in the given function
    static int findTrailingZeros(int n)
    {
        // If n is odd
        if ((n & 1) == 1)
            return 0;
     
        // If n is even
        else
        {
            int ans = 0;
     
            // Find the trailing zeros
            // in n/2 factorial
            n /= 2;
            while (n != 0)
            {
                ans += n / 5;
                n /= 5;
            }
     
            // Return the required answer
            return ans;
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 12;
     
        System.out.println(findTrailingZeros(n));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to return the count of
# trailing 0s in the given function
def findTrailingZeros(n):
     
    # If n is odd
    if (n & 1):
        return 0
 
    # If n is even
    else:
        ans = 0
 
        # Find the trailing zeros
        # in n/2 factorial
        n //= 2
        while (n):
            ans += n // 5
            n //= 5
 
        # Return the required answer
        return ans
 
# Driver code
 
n = 12
 
print(findTrailingZeros(n))
 
# This code is contributed by mohit kumar 29

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the count of
    // trailing 0s in the given function
    static int findTrailingZeros(int n)
    {
        // If n is odd
        if ((n & 1) == 1)
            return 0;
     
        // If n is even
        else
        {
            int ans = 0;
     
            // Find the trailing zeros
            // in n/2 factorial
            n /= 2;
            while (n != 0)
            {
                ans += n / 5;
                n /= 5;
            }
     
            // Return the required answer
            return ans;
        }
    }
     
    // Driver code
    public static void Main(String[] args)
    {
        int n = 12;
     
        Console.WriteLine(findTrailingZeros(n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Function to return the count of
// trailing 0s in the given function
function findTrailingZeros(n)
{
     
    // If n is odd
    if (n & 1)
        return 0;
 
    // If n is even
    else
    {
        let ans = 0;
 
        // Find the trailing zeros
        // in n/2 factorial
        n = parseInt(n / 2);
         
        while (n)
        {
            ans += parseInt(n / 5);
            n = parseInt(n / 5);
        }
 
        // Return the required answer
        return ans;
    }
}
 
// Driver code
let n = 12;
 
document.write(findTrailingZeros(n));
 
// This code is contributed by subhammahato348
 
</script>

1

Complejidad de tiempo: O (log ₅ n)

Espacio Auxiliar: O(1)