Números cuyos factoriales terminan en n ceros

Dado un entero n, necesitamos encontrar el número de enteros positivos cuyo factorial termine en n ceros.
Ejemplos: 
 

Input : n = 1
Output : 5 6 7 8 9
Explanation: Here, 5! = 120, 6! = 720,
7! = 5040, 8! = 40320 and 9! = 362880.

Input : n = 2
Output : 10 11 12 13 14 
          

Requisito previo: Ceros finales en factorial .
Enfoque ingenuo: podemos simplemente iterar a través del rango de enteros y encontrar el número de ceros finales de todos los números e imprimir los números con n ceros finales.
Enfoque eficiente: en este enfoque utilizamos la búsqueda binaria. Use la búsqueda binaria para todos los números en el rango y obtenga el primer número con n ceros al final. Encuentra todos los números con m ceros después de ese número.
 

C++

// Binary search based CPP program to find
// numbers with n trailing zeros.
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate trailing zeros
int trailingZeroes(int n)
{
    int cnt = 0;
    while (n > 0) {
        n /= 5;
        cnt += n;
    }
    return cnt;
}
 
void binarySearch(int n)
{
    int low = 0;
    int high = 1e6; // range of numbers
 
    // binary search for first number with
    // n trailing zeros
    while (low < high) {
        int mid = (low + high) / 2;
        int count = trailingZeroes(mid);
        if (count < n)
            low = mid + 1;
        else
            high = mid;
    }
 
    // Print all numbers after low with n
    // trailing zeros.
    vector<int> result;
    while (trailingZeroes(low) == n) {
        result.push_back(low);
        low++;
    }
 
    // Print result
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << " ";
}
 
// Driver code
int main()
{
    int n = 2;
    binarySearch(n);
    return 0;
}

Java

// Binary search based Java
// program to find numbers
// with n trailing zeros.
import java.io.*;
 
class GFG {
 
    // Function to calculate
    // trailing zeros
    static int trailingZeroes(int n)
    {
        int cnt = 0;
        while (n > 0)
        {
            n /= 5;
            cnt += n;
        }
        return cnt;
    }
 
    static void binarySearch(int n)
    {
        int low = 0;
         
        // range of numbers
        int high = 1000000;
 
        // binary search for first number
        // with n trailing zeros
        while (low < high) {
            int mid = (low + high) / 2;
            int count = trailingZeroes(mid);
            if (count < n)
                low = mid + 1;
            else
                high = mid;
        }
 
        // Print all numbers after low
        // with n trailing zeros.
        int result[] = new int[1000];
        int k = 0;
        while (trailingZeroes(low) == n) {
            result[k] = low;
            k++;
            low++;
        }
 
        // Print result
        for (int i = 0; i < k; i++)
            System.out.print(result[i] + " ");
    }
 
    // Driver code
    public static void main(String args[])
    {
        int n = 3;
        binarySearch(n);
    }
}
 
// This code is contributed
// by Nikita Tiwari.

Python3

# Binary search based Python3 code to find
# numbers with n trailing zeros.
 
# Function to calculate trailing zeros
def trailingZeroes( n ):
    cnt = 0
    while n > 0:
        n =int(n/5)
        cnt += n
    return cnt
 
def binarySearch( n ):
    low = 0
    high = 1e6  # range of numbers
     
    # binary search for first number with
    # n trailing zeros
    while low < high:
        mid = int((low + high) / 2)
        count = trailingZeroes(mid)
        if count < n:
            low = mid + 1
        else:
            high = mid
             
    # Print all numbers after low with n
    # trailing zeros.
    result = list()
    while trailingZeroes(low) == n:
        result.append(low)
        low+=1
     
    # Print result
    for i in range(len(result)):
        print(result[i],end=" ")
 
# Driver code
n = 2
binarySearch(n)
 
# This code is contributed by "Sharad_Bhardwaj".

C#

// Binary search based C#
// program to find numbers
// with n trailing zeros.
using System;
 
class GFG {
 
    // Function to calculate
    // trailing zeros
    static int trailingZeroes(int n)
    {
        int cnt = 0;
         
        while (n > 0)
        {
            n /= 5;
            cnt += n;
        }
         
        return cnt;
    }
 
    static void binarySearch(int n)
    {
        int low = 0;
         
        // range of numbers
        int high = 1000000;
 
        // binary search for first number
        // with n trailing zeros
        while (low < high) {
            int mid = (low + high) / 2;
            int count = trailingZeroes(mid);
             
            if (count < n)
                low = mid + 1;
            else
                high = mid;
        }
 
        // Print all numbers after low
        // with n trailing zeros.
        int []result = new int[1000];
        int k = 0;
        while (trailingZeroes(low) == n) {
            result[k] = low;
            k++;
            low++;
        }
 
        // Print result
        for (int i = 0; i < k; i++)
            Console.Write(result[i] + " ");
    }
 
    // Driver code
    public static void Main()
    {
        int n = 2;
         
        binarySearch(n);
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// Binary search based PHP program to
// find numbers with n trailing zeros.
 
// Function to calculate trailing zeros
function trailingZeroes($n)
{
    $cnt = 0;
    while ($n > 0)
    {
        $n = intval($n / 5);
        $cnt += $n;
    }
    return $cnt;
}
 
function binarySearch($n)
{
    $low = 0;
    $high = 1e6; // range of numbers
 
    // binary search for first number
    // with n trailing zeros
    while ($low < $high)
    {
        $mid = intval(($low + $high) / 2);
        $count = trailingZeroes($mid);
        if ($count < $n)
            $low = $mid + 1;
        else
            $high = $mid;
    }
 
    // Print all numbers after low with n
    // trailing zeros.
    $result = array();
    while (trailingZeroes($low) == $n)
    {
        array_push($result, $low);
        $low++;
    }
 
    // Print result
    for ($i = 0;
         $i < sizeof($result); $i++)
        echo $result[$i] . " ";
}
 
// Driver code
$n = 2;
binarySearch($n);
 
// This code is contributed by Ita_c
?>

Javascript

<script>
 
// Binary search based JavaScript program to find
// numbers with n trailing zeros.
 
// Function to calculate trailing zeros
function trailingZeroes(n)
{
    var cnt = 0;
    while (n > 0) {
        n = parseInt(n/5);
        cnt += n;
    }
    return cnt;
}
 
function binarySearch(n)
{
    var low = 0;
    var high = 1e6; // range of numbers
 
    // binary search for first number with
    // n trailing zeros
    while (low < high) {
        var mid = parseInt((low + high) / 2);
        var count = trailingZeroes(mid);
        if (count < n)
            low = mid + 1;
        else
            high = mid;
    }
 
    // Print all numbers after low with n
    // trailing zeros.
    var result = [];
    while (trailingZeroes(low) == n) {
        result.push(low);
        low++;
    }
 
    // Print result
    for (var i = 0; i < result.length; i++)
        document.write( result[i] + " ");
}
 
// Driver code
var n = 2;
binarySearch(n);
 
 
</script>

Producción: 

10 11 12 13 14 

Publicación traducida automáticamente

Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *