En este problema en particular te solicitan calcular el último digito del factorial del número, por lo tanto no es necesario calcular el valor del factorial, que ya has visto que lleva demasiado tiempo de procesamiento y/o memoria.
Para resolver el problema, en primer lugar deberías leer sobre aritmética modular.
Dos números son congruentes módulo n si tienen el mismo resto después de dividir a cada uno de ellos por n. Por ejemplo, 9 y 17 son congruentes módulo 4, ya que ambos dan como resto 1 después de dividirlos por 4. 9/4 = 2, resto 1, y 17/4 = 4, resto 1.
Se define el operador módulo (en java se utiliza el símbolo %
) para obtener el resto de una división entera. Por ejemplo, si calculamos i = 6 % 4
obtendríamos como resultado que i
vale 2, que es el resto de la división entre 6 y 4.
El sistema de numeración que utilizamos es de base 10, por lo tanto, para obtener el último dígito de un número, solamente deberíamos calcular el valor del resto de dividir ese número entre 10. Por ejemplo, para saber el último dígito del número 145, calculamos el resto de la división 145/10, y obtenemos 5. Esto se comprueba fácilmente, ya que 145 = 14*10 + 5.
Ya estamos mas cerca de resolver el problema. Ahora falta ver qué pasa cuando hay una operación de multiplicación. Para el problema del factorial, ya sabes que factorial(n) se calcula como 1*2*...*(n-1)*n. Pero como dice el enunciado, solamente nos interesa el último dígito de este resultado.
De acuerdo a las clases de equivalencia que están en el artículo de wikipedia que enlacé más arriba, resulta ser que para calcular el producto modulo n de dos números, solamente basta con calcular el producto de cada uno de ellos módulo n.
Esto quiere decir, por ejemplo, que si necesitamos calcular el último dígito de 173*265 (que da como resultado 45845, y el último dígito es 5) podemos operar directamente como 173*265 (mod 10), o bien como (173 (mod 10) * 265 (mod 10)) (mod 10). Si haces el cálculo, ambos resultados dan 5. Te invito a que no me creas, y lo compruebes por tí mismo.
En resumen, no es necesario almacenar todo el número si lo único que necesitas es el último dígito. Con almacenar el último dígito de cada producto, y utilizando aritmética modular, puedes calcular el último dígito del factorial de cualquier número, sin necesidad de BigIntegers, en tiempos relativamente cercanos a 0 segundos.
Edito: Agrego el código.
int ultimodigito = 1;
for(int i = 1; i <= n; i++) {
ultimodigito = (ultimodigito * i) % 10;
}
Y como dije en los comentarios, el factorial de cualquier número mayor o igual a 5 tiene que terminar en cero porque contiene el producto 5*2. En ese caso, este código es mucho más rápido:
int ultimodigito = 0;
int[] menoresa5 = {1, 1, 2, 6, 4};
if(n > 4) {
ultimodigito = 0;
} else {
ultimodigito = menoresa5[n];
}
El arreglo menoresa5
contiene los últimos dígitos de 0! hasta 4!.
for
.int
. El máximo valor de un etero positivo en Java es:2147483647
. El número13!
es6227020800
que ya sobrepasa el máximo valor de unint
.