Dado un número n. La tarea es encontrar el número más pequeño cuyo factorial contenga al menos n dígitos.
Ejemplos:
Input : n = 1 Output : 0 0! = 1, hence it has 1 digit. Input : n = 2 Output : 4 4! = 24 and 3! = 6, hence 4 is the smallest number having 2 digits in its factorial Input : n = 5 Output : 8
En el artículo Contar dígitos en un factorial de un número, hemos discutido cómo podemos encontrar eficientemente el número de dígitos en un factorial.
Usamos la siguiente fórmula para encontrar el número de dígitos
Kamenetsky’s formula approximates the number of digits in a factorial by : f(x) = log10(((n/e)n) * sqrt(2*pi*n)) Thus, we can pretty easily use the property of logarithms to , f(x) = n*log10((n/e)) + log10(2*pi*n)/2
Ahora necesitamos determinar el intervalo en el que podemos encontrar un factorial que tenga al menos n dígitos. Las siguientes son algunas observaciones:
- Para un número grande siempre podemos decir que su factorial tiene más dígitos que el propio número. Por ejemplo factorial de 100 tiene 158 dígitos que es mayor que 100.
- Sin embargo, para números más pequeños, ese podría no ser el caso. Por ejemplo, el factorial de 8 tiene solo 5 dígitos, que es menor que 8. De hecho, los números hasta el 21 siguen esta tendencia.
Por lo tanto, si buscamos desde 0! a n! para encontrar un resultado que tenga al menos n dígitos, no podremos encontrar el resultado para números más pequeños.
Por ejemplo, supongamos que n = 5, ahora que estamos buscando en [0, n], el número máximo de dígitos que podemos obtener es 3 (¡encontrado en 5! = 120). Sin embargo, si buscamos en [0, 2*n] (0 a 10), ¡podemos encontrar 8! tiene 5 dígitos.
Por lo tanto, si podemos buscar todos los factoriales de 0 a 2*n, siempre habrá un número k que tendrá al menos n dígitos en su factorial. (Se recomienda a los lectores que intenten resolver este hecho por su cuenta)
We can say conclude if we have to find a number k, such that k! has at least n digits, we can be sure that k lies in [0,2*n] i.e., 0<= k <= 2*n
Por lo tanto, podemos hacer una búsqueda binaria entre 0 y 2*n para encontrar el número más pequeño que tenga al menos n dígitos.
C++
// A C++ program to find the smallest number
// having at least n digits in factorial
#include <bits/stdc++.h>
using namespace std;
// Returns the number of digits present in n!
int findDigitsInFactorial(int n)
{
// factorial of -ve number doesn't exists
if (n < 0)
return 0;
// base case
if (n <= 1)
return 1;
// Use Kamenetsky formula to calculate the
// number of digits
double x = ((n*log10(n/M_E)+log10(2*M_PI*n)/2.0));
return floor(x)+1;
}
// This function receives an integer n and returns
// an integer whose factorial has at least n digits
int findNum(int n)
{
// (2*n)! always has more digits than n
int low = 0, hi = 2*n;
// n <= 0
if (n <= 0)
return -1;
// case for n = 1
if (findDigitsInFactorial(low) == n)
return low;
// now use binary search to find the number
while (low <= hi)
{
int mid = (low+hi) / 2;
// if (mid-1)! has lesser digits than n
// and mid has n or more then mid is the
// required number
if (findDigits(mid) >= n && findDigits(mid-1)<n)
return mid;
else if (findDigits(mid) < n)
low = mid+1;
else
hi = mid-1;
}
return low;
}
// Driver program to check the above functions
int main()
{
cout << findNum(1) << endl;
cout << findNum(2) << endl;
cout << findNum(5) << endl;
cout << findNum(24) << endl;
cout << findNum(100) << endl;
cout << findNum(1221) << endl;
return 0;
}
Java
// A Java program to find the
// smallest number having at
// least n digits in factorial
class GFG
{
// Returns the number of
// digits present in n!
static int findDigitsInFactorial(int n)
{
// factorial of -ve number
// doesn't exists
if (n < 0)
return 0;
// base case
if (n <= 1)
return 1;
// Use Kamenetsky formula to
// calculate the number of digits
double x = ((n * Math.log10(n / Math.E) +
Math.log10(2 * Math.PI * n) / 2.0));
return (int)(Math.floor(x) + 1);
}
// This function receives an integer
// n and returns an integer whose
// factorial has at least n digits
static int findNum(int n)
{
// (2*n)! always has
// more digits than n
int low = 0, hi = 2 * n;
// n <= 0
if (n <= 0)
return -1;
// case for n = 1
if (findDigitsInFactorial(low) == n)
return low;
// now use binary search
// to find the number
while (low <= hi)
{
int mid = (low + hi) / 2;
// if (mid-1)! has lesser digits
// than n and mid has n or more
// then mid is the required number
if (findDigitsInFactorial(mid) >= n &&
findDigitsInFactorial(mid - 1) < n)
return mid;
else if (findDigitsInFactorial(mid) < n)
low = mid + 1;
else
hi = mid - 1;
}
return low;
}
// Driver Code
public static void main(String[] args)
{
System.out.println(findNum(1));
System.out.println(findNum(2));
System.out.println(findNum(5));
System.out.println(findNum(24));
System.out.println(findNum(100));
System.out.println(findNum(1221));
}
}
// This Code is Contributed by mits
Python3
# Python3 program to find the # smallest number # having at least n digits # in factorial import math # Returns the number of digits # present in n! def findDigitsInFactorial(n): # factorial of -ve number # doesn't exists if (n < 0): return 0 # base case if (n <= 1): return 1 # Use Kamenetsky formula to calculate the # number of digits M_E=2.7182818284590452354 M_PI=3.14159265358979323846 x = ((n*math.log10(n/M_E)+math.log10(2*M_PI*n)/2.0)) return int(math.floor(x)+1) # This function receives an # integer n and returns # an integer whose factorial has # at least n digits def findNum(n): # (2*n)! always has more # digits than n low = 0 hi = 2*n # n <= 0 if (n <= 0): return -1 # case for n = 1 if (findDigitsInFactorial(low) == n): return int(round(low)) # now use binary search to # find the number while (low <= hi): mid = int((low+hi) / 2) # if (mid-1)! has lesser digits than n # and mid has n or more then mid is the # required number if ((findDigitsInFactorial(mid) >= n and findDigitsInFactorial(mid-1)<n)): return int(round(mid)) elif (findDigitsInFactorial(mid) < n): low = mid+1 else: hi = mid-1 return int(round(low)) # Driver code if __name__=='__main__': print(findNum(1)); print(findNum(2)); print(findNum(5)); print(findNum(24)); print(findNum(100)); print(findNum(1221)); # this code is contributed by # mits
C#
// A C# program to find the
// smallest number having at
// least n digits in factorial
using System;
class GFG
{
// Returns the number of
// digits present in n!
static int findDigitsInFactorial(int n)
{
// factorial of -ve number
// doesn't exists
if (n < 0)
return 0;
// base case
if (n <= 1)
return 1;
// Use Kamenetsky formula to
// calculate the number of digits
double x = ((n * Math.Log10(n / Math.E) +
Math.Log10(2 * Math.PI * n) / 2.0));
return (int)(Math.Floor(x) + 1);
}
// This function receives an integer
// n and returns an integer whose
// factorial has at least n digits
static int findNum(int n)
{
// (2*n)! always has
// more digits than n
int low = 0, hi = 2 * n;
// n <= 0
if (n <= 0)
return -1;
// case for n = 1
if (findDigitsInFactorial(low) == n)
return low;
// now use binary search
// to find the number
while (low <= hi)
{
int mid = (low + hi) / 2;
// if (mid-1)! has lesser digits
// than n and mid has n or more
// then mid is the required number
if (findDigitsInFactorial(mid) >= n &&
findDigitsInFactorial(mid - 1) < n)
return mid;
else if (findDigitsInFactorial(mid) < n)
low = mid + 1;
else
hi = mid - 1;
}
return low;
}
// Driver Code
static public void Main ()
{
Console.WriteLine(findNum(1));
Console.WriteLine(findNum(2));
Console.WriteLine(findNum(5));
Console.WriteLine(findNum(24));
Console.WriteLine(findNum(100));
Console.WriteLine(findNum(1221));
}
}
// This code is contributed by akt_mit
PHP
<?php
// A PHP program to find the smallest number
// having at least n digits in factorial
// Returns the number of digits
// present in n!
function findDigitsInFactorial($n)
{
// factorial of -ve number
// doesn't exists
if ($n < 0)
return 0;
// base case
if ($n <= 1)
return 1;
// Use Kamenetsky formula to
// calculate the number of digits
$x = (($n * log10($n / M_E) +
log10(2 * M_PI * $n) / 2.0));
return (int)(floor($x) + 1);
}
// This function receives an integer
// n and returns an integer whose
// factorial has at least n digits
function findNum($n)
{
// (2*n)! always has more
// digits than n
$low = 0;
$hi = 2 * $n;
// n <= 0
if ($n <= 0)
return -1;
// case for n = 1
if (findDigitsInFactorial($low) == $n)
return (int)round($low);
// now use binary search to
// find the number
while ($low <= $hi)
{
$mid = ($low + $hi) / 2;
// if (mid-1)! has lesser digits
// than n and mid has n or more
// then mid is the required number
if (findDigitsInFactorial($mid) >= $n &&
findDigitsInFactorial($mid - 1) < $n)
return (int)round($mid);
else if (findDigitsInFactorial($mid) < $n)
$low = $mid + 1;
else
$hi = $mid - 1;
}
return (int)round($low);
}
// Driver Code
echo findNum(1) . "\n";
echo findNum(2) . "\n";
echo findNum(5) . "\n";
echo findNum(24) . "\n";
echo findNum(100) . "\n";
echo findNum(1221) . "\n";
// This code is contributed by mits
?>
Javascript
<script>
// A Javascript program to find the smallest number
// having at least n digits in factorial
// Returns the number of digits present in n!
function findDigitsInFactorial(n)
{
// factorial of -ve number doesn't exists
if (n < 0)
return 0;
// base case
if (n <= 1)
return 1;
// Use Kamenetsky formula to calculate the
// number of digits
let x = (n*Math.log10(n/Math.E)+Math.log10(2*Math.PI*n)/2.0);
return Math.floor(x)+1;
}
// This function receives an integer n and returns
// an integer whose factorial has at least n digits
function findNum(n)
{
// (2*n)! always has more digits than n
let low = 0, hi = 2*n;
// n <= 0
if (n <= 0)
return -1;
// case for n = 1
if (findDigitsInFactorial(low) == n)
return low;
// now use binary search to find the number
while (low <= hi)
{
let mid = (low+hi) / 2;
// if (mid-1)! has lesser digits than n
// and mid has n or more then mid is the
// required number
if (findDigitsInFactorial(mid) >= n && findDigitsInFactorial(mid-1)<n)
return Math.floor(mid);
else if (findDigitsInFactorial(mid) < n)
low = mid+1;
else
hi = mid-1;
}
return low;
}
// Driver program to check the above functions
document.write(findNum(1) + "<br>");
document.write(findNum(2) + "<br>");
document.write(findNum(5) + "<br>");
document.write(findNum(24) + "<br>");
document.write(findNum(100) + "<br>");
document.write(findNum(1221) + "<br>");
// This code is contributed by Mayank Tyagi
</script>
Producción:
0 4 8 24 70 532
Análisis de Complejidad
La complejidad para la búsqueda binaria es O(log(2*n)), si ignoramos la complejidad de la función logarítmica. Por lo tanto, la complejidad general es O (log (n)).
Complejidad espacial : O(1) ya que usa espacio constante
Ashutosh Kumar contribuye con este artículo. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando write.geeksforgeeks.org o enviar su 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