Sum of Digits
Recibes un entero no negativo n. Devuelve la suma de sus dígitos decimales. Por ejemplo, los dígitos de 482 son 4, 8 y 2, así que la respuesta es 14.
Función
- ninteger
- el entero no negativo cuyos dígitos sumas
- Devuelveinteger
- la suma de los dígitos decimales de n
Restricciones
0 ≤ n ≤ 231-1
Ejemplos
- Entrada
- n = 9045
- Salida
- 18
- Explicación
- Los dígitos de
9045son 9, 0, 4 y 5, y9 + 0 + 4 + 5 = 18. El cero no suma nada, pero aun así cuenta como dígito.
- Entrada
- n = 7
- Salida
- 7
- Explicación
- Un número de un dígito es igual a la suma de sus dígitos, así que
7da7.
+15 pruebas ocultas al enviar
Pistas
Ábrelas de una en una. Cada una revela un poco más.
¿Cómo encuentras el último dígito de un número con una operación aritmética?
El último dígito es
n % 10, y la división entera entre 10 lo elimina. Cada par de operaciones te da un dígito.Mantén un total acumulado. Mientras
nsea mayor que 0, súmalen % 10y dividenentre 10, redondeando hacia abajo.
Solución
Un número no te da sus dígitos uno por uno; tienes que descomponerlo. Puedes convertirlo en texto y leer los caracteres, o usar las dos operaciones aritméticas que extraen el último dígito: n % 10 lo obtiene, y la división entera por 10 lo elimina. Ambas requieren un paso por dígito, representado abajo por d, y aquí d ≤ 10. La versión aritmética no necesita memoria adicional.
Lee los dígitos como texto
Intuición
Cuando escribes un número, ya ves sus dígitos. Convierte n en su representación decimal como texto: 9045 se convierte en los cuatro caracteres 9, 0, 4 y 5; después, recorre los caracteres y suma el valor de cada uno.
Un carácter todavía no es un número. El carácter '4' se almacena como el código 52, así que lo analizas o restas el código de '0': '4' - '0' = 4. Los caracteres de los dígitos tienen códigos consecutivos, por eso esa resta funciona para los diez.
El texto tiene d caracteres, uno por dígito, así que el bucle tarda O(d) y el texto en sí ocupa O(d) espacio adicional.
Algoritmo
- Convierte
nen su representación decimal en texto. - Establece
total = 0. - Por cada carácter, suma su valor numérico a
total. - Devuelve
total.
def sumOfDigits(n):
total = 0
for digit in str(n):
total += int(digit)
return totalQuita el último dígito con % 10
Intuición
Puedes separar un número sin ningún texto. El resto de una división entre 10 es el último dígito: 9045 % 10 = 5. La división entera entre 10 elimina ese dígito: 9045 / 10 = 904 cuando se descarta la fracción. Repite el par y los dígitos salen de derecha a izquierda.
Para 9045: suma 5 y conserva 904, suma 4 y conserva 90, suma 0 y conserva 9, suma 9 y conserva 0. El bucle se detiene en 0 con un total de 18. Para n = 0, el bucle nunca se ejecuta y la respuesta es 0, lo cual es correcto.
Cada paso elimina un dígito, así que hay d pasos, tiempo O(d) y solo dos enteros en memoria, espacio O(1). Cada valor intermedio es menor que n, así que nada puede desbordarse.
Algoritmo
- Establece
total = 0. - Mientras
n > 0, suman % 10atotal. - Divide
nentre 10, descartando la parte fraccionaria. - Cuando
nllegue a 0, devuelvetotal.
def sumOfDigits(n):
total = 0
while n > 0:
total += n % 10 # last digit
n //= 10 # drop the last digit
return total
Errores comunes y casos límite
El bucle es corto, y los errores tienen que ver con los tipos y con la entrada más pequeña.
- Usar
/cuando el lenguaje significa división real. En JavaScript, TypeScript, Lua, PHP y R,9045 / 10es904.5, y el bucle después suma fracciones. Redondea hacia abajo conMath.flooromath.floor; en Python usa//, en Dart~/, en PHPintdiv, en R%/%. - Sumar caracteres en vez de dígitos. El carácter
'7'tiene el código 55, no 7. Resta'0'o analiza primero el carácter. - Continuar el bucle mientras
n >= 10. El bucle después se detiene con el dígito inicial todavía enny nunca lo suma, así que9045da 9 en lugar de 18. Continúa el bucle mientrasn > 0, lo que también devuelve 0 paran = 0. - Imprimir números grandes como texto en R.
as.character(100000)da"1e+05", no los seis dígitos del número. Usaformat(n, scientific = FALSE).
Preguntas frecuentes4
¿Cuál es la complejidad temporal de sumar los dígitos de un número?
Un paso por dígito, así que O(d), donde d es el número de dígitos. Un número n tiene aproximadamente log10(n) + 1 dígitos, por lo que el mismo límite suele escribirse como O(log n). Para un entero de 32 bits, son como máximo 10 pasos.
¿Cómo obtienes los dígitos de un número sin convertirlo en una cadena?
Usa el resto y la división entera entre 10. n % 10 es el último dígito, y dividir n entre 10 descartando el resto elimina ese dígito. Repite hasta que n llegue a 0, y recorrerás todos los dígitos de derecha a izquierda.
¿Cuál es la raíz digital de un número?
Es lo que obtienes al sumar los dígitos una y otra vez hasta que queda un solo dígito: 9045 da 18 y después 9. Para un n positivo, es igual a 1 + (n-1) % 9, porque todo número deja el mismo resto al dividirlo entre 9 que la suma de sus dígitos.
¿Es mejor la versión con cadenas o la versión aritmética?
Ambas son O(d) y ambas son correctas. La versión con cadenas es más corta de escribir en muchos lenguajes, pero crea una copia de los dígitos. La versión aritmética usa O(1) de memoria adicional y le muestra al entrevistador que sabes cómo % 10 y / 10 descomponen un número, algo que vuelve a ser útil en los problemas de palíndromos e inversión de dígitos.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def sumOfDigits(n):
# Escribe el código aquíCaso 1
Caso 2
Entrada
n = 9045
Esperado
18