Suma de dígitos repetida
La misión
Problema
Toma un número entero no negativo y suma sus dígitos decimales. Si el resultado tiene más de un dígito, vuelve a sumar sus dígitos, y sigue así hasta que quede un solo dígito. Devuelve ese dígito, idealmente sin usar ningún bucle.
Ejemplos
Input: n = 38
Output: 2
Por qué: 3 + 8 = 11, luego 1 + 1 = 2
Input: n = 99999
Output: 9
Por qué: los dígitos suman 45, y 4 + 5 = 9
Input: n = 0
Output: 0
Por qué: caso límite: cero ya es un solo dígito y es el único número que termina en 0
Pistas
0 / 3
Simular el proceso es fácil. La pregunta interesante es si el dígito final puede predecirse directamente a partir del número.
Diez deja resto uno al dividirlo entre nueve, y lo mismo pasa con cada potencia de diez. Piensa en qué te dice eso sobre un número y la suma de sus dígitos.
Un número y la suma de sus dígitos dejan el mismo resto módulo nueve, así que el dígito final queda determinado por n módulo 9. Convierte un resto de cero en 9 para los números positivos y trata aparte n igual a 0; la expresión 1 más (n menos 1) módulo 9 hace ambas conversiones a la vez.
- Tiempo objetivo
- O(1)
- Espacio objetivo
- O(1)
Restricciones
- n ≥ 0
Solución
Cada potencia de diez es uno más que un múltiplo de nueve, así que un número y la suma de sus dígitos dejan el mismo resto módulo nueve, y ese resto sobrevive a cada ronda del proceso. Por lo tanto, el dígito final es el único dígito del 1 al 9 con el mismo resto que n, que es 1 más (n menos 1) módulo 9, y el cero es el único número que termina en 0. No hace falta ningún bucle. El tiempo y el espacio son O(1).
def digit_root(n):
if n == 0:
return 0 # the only number whose digits sum to 0
return 1 + (n - 1) % 9 # digit sums preserve the remainder mod 9
print(digit_root(38)) # -> 2
print(digit_root(99999)) # -> 9
print(digit_root(0)) # -> 0
print(digit_root(9)) # -> 9¿Lo que te frena es la idea y no el código? Aritmética modular lo explica.