Medio–difícil · el truco es aritmético
Ceros finales
La entrada es demasiado grande para calcularla. No es un defecto del problema: es el problema diciéndote que la respuesta no está en el cálculo.
En una fraseLos ceros finales vienen de los factores 5, así que la respuesta es n/5 + n/25 + n/125 + …: nunca calcules n!, que para n hasta 10⁹ es astronómico.
El problema
Entrada: Un entero n (1 ≤ n ≤ 1,000,000,000).
Salida: Cuántos ceros finales tiene n!, donde n! = 1 × 2 × … × n.
Ejemplos:
| Entrada | Salida |
|---|---|
5 | 1 |
10 | 2 |
25 | 6 |
10! = 3628800 → dos ceros. 25! = 15511210043330985984000000 → seis. Ojo: 25/5 solo da 5; el sexto cero viene de que 25 aporta dos factores de 5.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — Un cero final es un factor de 10
Cada cero final significa que el número es divisible por otro 10, y 10 = 2 × 5. Así que la pregunta pasa a ser: ¿cuántos pares (2, 5) hay escondidos en n!? Como los pares abundan mucho más que los múltiplos de 5, el número de 5 es el limitante: basta con contar los 5.
Pista 2 — No es n/5, esa es la trampa
n / 5 cuenta los múltiplos de 5, pero 25 aporta dos 5, 125 aporta tres, etc. Suma n / 25, luego n / 125, y sigue. El bucle queda precioso: while (n > 0) { n /= 5; zeros += n; }, dividiendo n mismo y acumulando.
Pista 3 — Por qué no debes recorrer de 1 a n
Multiplicar 1 × 2 × … × 1,000,000,000 son 109 iteraciones, y el número desbordaría cualquier tipo entero mucho antes. Aunque cupiera, la pestaña se congelaría. Cuando el rango de entrada hace imposible la fuerza bruta, eso es una pista: la solución buscada es O(log n) u O(1).
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long zeros = 0;
while (n > 0) {
n = n / 5;
zeros = zeros + n;
}
cout << zeros << endl;
return 0;
}Es el último problema de la cadena, y encaja: sin arrays, sin recorrer la entrada, sin recursión, solo una observación que cambia mil millones de multiplicaciones por una docena de divisiones. Esa es la diferencia entre alguien que sabe programar y alguien que escribe código: el segundo ve que la pregunta nunca fue sobre el factorial. Vuelve a la lista y mira cuántos puedes hacer ya sin pistas.
Análisis profundo
Por qué funciona
Cada cero final es un factor de 10, y 10 = 2 × 5. Los pares abundan mucho más que los múltiplos de 5, así que los 5 son el limitante: cuenta esos.
El coste
O(log_5 n): doce divisiones para mil millones. Multiplicar de 1 a n serían 10^9 multiplicaciones, y el número desbordaría mucho antes.
Dónde falla
- Calcular solo
n / 5se pierde el 5 extra que aporta 25 y los dos que aporta 125: ya falla en n = 25. - Intentar calcular n! de verdad: con mil millones desborda cualquier tipo entero y congela la pestaña. Un rango de entrada que descarta la fuerza bruta <em>es</em> la pista.
Siguiente paso
Aquí termina la cadena. Mira el primer problema y fíjate en lo lejos que has llegado.
Dos cosas para recordar
- Ceros finales = pares de 2×5, y el 5 es el lado escaso.
n / 5no basta: tambiénn / 25,n / 125…
🐞 Esta versión falla: ábrela y pruébala
Solo n / 5: se pierden los 5 extra de 25, 125, 625…
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long zeros = n / 5;
cout << zeros << endl;
return 0;
}