Dado un número n . La tarea es encontrar el número más pequeño cuyo factorial contenga al menos n ceros finales.
Ejemplos:
Input : n = 1 Output : 5 1!, 2!, 3!, 4! does not contain trailing zero. 5! = 120, which contains one trailing zero. Input : n = 6 Output : 25
En el artículo para Contar ceros finales en el factorial de un número , hemos discutido que el número de ceros es igual al número de 5 en factores primos de x. Hemos discutido a continuación la fórmula para contar el número de 5.
Trailing 0s in x! = Count of 5s in prime factors of x!
= floor(x/5) + floor(x/25) + floor(x/125) + ....
Tomemos algunos ejemplos para observar el patrón.
5! has 1 trailing zeroes [All numbers from 6 to 9 have 1 trailing zero] 10! has 2 trailing zeroes [All numbers from 11 to 14 have 2 trailing zeroes] 15! to 19! have 3 trailing zeroes 20! to 24! have 4 trailing zeroes 25! to 29! have 6 trailing zeroes
Podemos notar que el valor máximo cuyo factorial contiene n ceros finales es 5*n.
Entonces, para encontrar el valor mínimo cuyo factorial contiene n ceros finales, use la búsqueda binaria en el rango de 0 a 5*n. Y encuentre el número más pequeño cuyo factorial contenga n ceros finales.
C++
// C++ program to find smallest number whose
// factorial contains at least n trailing
// zeroes.
#include<bits/stdc++.h>
using namespace std;
// Return true if number's factorial contains
// at least n trailing zero else false.
bool check(int p, int n)
{
int temp = p, count = 0, f = 5;
while (f <= temp)
{
count += temp/f;
f = f*5;
}
return (count >= n);
}
// Return smallest number whose factorial
// contains at least n trailing zeroes
int findNum(int n)
{
// If n equal to 1, return 5.
// since 5! = 120.
if (n==1)
return 5;
// Initialising low and high for binary
// search.
int low = 0;
int high = 5*n;
// Binary Search.
while (low <high)
{
int mid = (low + high) >> 1;
// Checking if mid's factorial contains
// n trailing zeroes.
if (check(mid, n))
high = mid;
else
low = mid+1;
}
return low;
}
// driver code
int main()
{
int n = 6;
cout << findNum(n) << endl;
return 0;
}
Java
// Java program to find smallest number whose
// factorial contains at least n trailing
// zeroes.
class GFG
{
// Return true if number's factorial contains
// at least n trailing zero else false.
static boolean check(int p, int n)
{
int temp = p, count = 0, f = 5;
while (f <= temp)
{
count += temp / f;
f = f * 5;
}
return (count >= n);
}
// Return smallest number whose factorial
// contains at least n trailing zeroes
static int findNum(int n)
{
// If n equal to 1, return 5.
// since 5! = 120.
if (n==1)
return 5;
// Initialising low and high for binary
// search.
int low = 0;
int high = 5 * n;
// Binary Search.
while (low < high)
{
int mid = (low + high) >> 1;
// Checking if mid's factorial
// contains n trailing zeroes.
if (check(mid, n))
high = mid;
else
low = mid + 1;
}
return low;
}
// Driver code
public static void main (String[] args)
{
int n = 6;
System.out.println(findNum(n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find smallest # number whose # factorial contains at least # n trailing zeroes # Return true if number's factorial contains # at least n trailing zero else false. def check(p,n): temp = p count = 0 f = 5 while (f <= temp): count += temp//f f = f*5 return (count >= n) # Return smallest number whose factorial # contains at least n trailing zeroes def findNum(n): # If n equal to 1, return 5. # since 5! = 120. if (n==1): return 5 # Initializing low and high for binary # search. low = 0 high = 5*n # Binary Search. while (low <high): mid = (low + high) >> 1 # Checking if mid's factorial contains # n trailing zeroes. if (check(mid, n)): high = mid else: low = mid+1 return low # driver code n = 6 print(findNum(n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find smallest number whose
// factorial contains at least n trailing
// zeroes.
using System;
class GFG
{
// Return true if number's factorial contains
// at least n trailing zero else false.
static bool check(int p, int n)
{
int temp = p, count = 0, f = 5;
while (f <= temp)
{
count += temp / f;
f = f * 5;
}
return (count >= n);
}
// Return smallest number whose factorial
// contains at least n trailing zeroes
static int findNum(int n)
{
// If n equal to 1, return 5.
// since 5! = 120.
if (n == 1)
return 5;
// Initialising low and high for binary
// search.
int low = 0;
int high = 5 * n;
// Binary Search.
while (low < high)
{
int mid = (low + high) >> 1;
// Checking if mid's factorial
// contains n trailing zeroes.
if (check(mid, n))
high = mid;
else
low = mid + 1;
}
return low;
}
// Driver code
public static void Main ()
{
int n = 6;
Console.WriteLine(findNum(n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find smallest
// number whose factorial contains
// at least n trailing zeroes.
// Return true if number's
// factorial contains at
// least n trailing zero
// else false.
function check($p, $n)
{
$temp = $p; $count = 0; $f = 5;
while ($f <= $temp)
{
$count += $temp / $f;
$f = $f * 5;
}
return ($count >= $n);
}
// Return smallest number
// whose factorial contains
// at least n trailing zeroes
function findNum($n)
{
// If n equal to 1, return 5.
// since 5! = 120.
if ($n == 1)
return 5;
// Initialising low and high
// for binary search.
$low = 0;
$high = 5 * $n;
// Binary Search.
while ($low < $high)
{
$mid = ($low + $high) >> 1;
// Checking if mid's factorial
// contains n trailing zeroes.
if (check($mid, $n))
$high = $mid;
else
$low = $mid + 1;
}
return $low;
}
// Driver Code
$n = 6;
echo(findNum($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// JavaScript program to find smallest number whose
// factorial contains at least n trailing
// zeroes.
// Return true if number's factorial contains
// at least n trailing zero else false.
function check(p, n)
{
let temp = p, count = 0, f = 5;
while (f <= temp)
{
count += Math.floor(temp/f);
f = f*5;
}
return (count >= n);
}
// Return smallest number whose factorial
// contains at least n trailing zeroes
function findNum(n)
{
// If n equal to 1, return 5.
// since 5! = 120.
if (n==1)
return 5;
// Initialising low and high for binary
// search.
let low = 0;
let high = 5*n;
// Binary Search.
while (low <high)
{
let mid = (low + high) >> 1;
// Checking if mid's factorial contains
// n trailing zeroes.
if (check(mid, n))
high = mid;
else
low = mid+1;
}
return low;
}
// driver code
let n = 6;
document.write(findNum(n) + "<br>");
// This code is contributed by Surbhi Tyagi
</script>
Producción :
25
Complejidad de tiempo: O (log 2 N)
Tomamos log 2 N en la búsqueda binaria y nuestra función check() toma log 5 N de tiempo, por lo que la complejidad total del tiempo se convierte en log 2 N * log 5 N, que en un sentido más general puede escribirse como (logN) 2 , que también puede ser escrito como log 2 N.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA