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