Sum of Digits

Q: Qual é a complexidade de tempo para somar os dígitos de um número?

Um passo por dígito, ou seja, O(d) , em que d é o número de dígitos. Um número n tem cerca de log10(n) + 1 dígitos, então o mesmo limite costuma ser escrito como O(log n) . Para um inteiro de 32 bits, são no máximo 10 passos.

Q: Como obter os dígitos de um número sem convertê-lo em uma string?

Use o resto e a divisão inteira por 10. n % 10 é o último dígito, e dividir n por 10 descartando o resto remove esse dígito. Repita até que n chegue a 0, e você percorrerá todos os dígitos da direita para a esquerda.

Q: A versão com strings ou a versão aritmética é melhor?

Ambos são O(d) e ambos estão corretos. A versão com string é mais curta de escrever em muitas linguagens, mas cria uma cópia dos dígitos. A versão aritmética usa O(1) de memória extra e mostra ao entrevistador que você sabe como % 10 e / 10 decompõem um número, algo que volta a aparecer em problemas de palíndromo e inversão de dígitos.

InicianteMatemática e simulação

+10

Você recebe um número inteiro não negativo n. Retorne a soma de seus dígitos decimais. Por exemplo, os dígitos de 482 são 4, 8 e 2, então a resposta é 14.

Função

sumOfDigits(n: integer) → integer

ninteger: o número inteiro não negativo cujos dígitos você soma
Retornainteger: a soma dos dígitos decimais de n

Restrições

0 ≤ n ≤ 2³¹-1

Exemplos

Entrada: n = 9045
Saída: 18
Explicação: Os dígitos de 9045 são 9, 0, 4 e 5, e 9 + 0 + 4 + 5 = 18. O zero não acrescenta nada, mas ainda conta como um dígito.

Entrada: n = 7
Saída: 7
Explicação: Um número de um dígito é igual à soma de seus dígitos, então 7 resulta em 7.

+15 testes ocultos ao enviar

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Um número não fornece seus dígitos um por um; você precisa separá-lo. Você pode transformá-lo em texto e ler os caracteres, ou usar as duas operações aritméticas que removem o último dígito: n % 10 o obtém, e a divisão inteira por 10 o remove. Ambas levam uma etapa por dígito, indicado por d abaixo, e d ≤ 10 aqui. A versão aritmética não precisa de memória extra.

Leia os dígitos como texto

Intuição

Quando você escreve um número, já vê seus dígitos. Transforme n em seu texto decimal: 9045 se torna os quatro caracteres 9, 0, 4 e 5; depois, percorra os caracteres e some o valor de cada um.

Um caractere ainda não é um número. O caractere '4' é armazenado como o código 52, então você o converte ou subtrai o código de '0': '4' - '0' = 4. Os caracteres dos dígitos têm códigos consecutivos, por isso essa subtração funciona para os dez dígitos.

O texto tem d caracteres, um por dígito, então o loop leva O(d) de tempo, e o próprio texto ocupa O(d) de espaço extra.

Algoritmo

Converta n para seu texto decimal.
Defina total = 0.
Para cada caractere, some seu valor numérico a total.
Retorne total.

def sumOfDigits(n):
    total = 0
    for digit in str(n):
        total += int(digit)
    return total

Remova o último dígito com % 10

Intuição

Você pode decompor um número sem usar texto. O resto de uma divisão por 10 é o último dígito: 9045 % 10 = 5. A divisão inteira por 10 descarta esse dígito: 9045 / 10 = 904 quando a parte fracionária é descartada. Repita o par de operações e os dígitos serão obtidos da direita para a esquerda.

Para 9045: some 5 e mantenha 904, some 4 e mantenha 90, some 0 e mantenha 9, some 9 e mantenha 0. O loop para em 0 com um total de 18. Para n = 0, o loop nunca é executado e a resposta é 0, o que está correto.

Cada etapa remove um dígito, então há d etapas, tempo O(d) e apenas dois inteiros ficam na memória, espaço O(1). Todo valor intermediário é menor que n, então não pode ocorrer overflow.

Algoritmo

Defina total = 0.
Enquanto n > 0, adicione n % 10 a total.
Divida n por 10, descartando a parte fracionária.
Quando n chegar a 0, retorne total.

def sumOfDigits(n):
    total = 0
    while n > 0:
        total += n % 10  # last digit
        n //= 10         # drop the last digit
    return total

Armadilhas e casos extremos

O laço é curto, e os erros estão relacionados aos tipos e à menor entrada.

Usar / quando a linguagem significa divisão real. Em JavaScript, TypeScript, Lua, PHP e R, 9045 / 10 é 904.5, e o laço então soma frações. Arredonde para baixo com Math.floor ou math.floor; em Python, use //, em Dart, ~/, em PHP, intdiv, em R, %/%.
Somar caracteres em vez de dígitos. O caractere '7' tem código 55, não 7. Subtraia '0' ou converta o caractere primeiro.
Repetir enquanto n >= 10. O laço então para com o dígito mais à esquerda ainda em n e nunca o soma, então 9045 resulta em 9 em vez de 18. Repita enquanto n > 0, o que também retorna 0 para n = 0.
Exibir números grandes como texto em R. as.character(100000) resulta em "1e+05", não nos seis dígitos do número. Use format(n, scientific = FALSE).

Perguntas frequentes4

Qual é a complexidade de tempo para somar os dígitos de um número?

Um passo por dígito, ou seja, O(d), em que d é o número de dígitos. Um número n tem cerca de log10(n) + 1 dígitos, então o mesmo limite costuma ser escrito como O(log n). Para um inteiro de 32 bits, são no máximo 10 passos.

Como obter os dígitos de um número sem convertê-lo em uma string?

Use o resto e a divisão inteira por 10. n % 10 é o último dígito, e dividir n por 10 descartando o resto remove esse dígito. Repita até que n chegue a 0, e você percorrerá todos os dígitos da direita para a esquerda.

Qual é a raiz digital de um número?

É o resultado de somar os dígitos repetidamente até restar um único dígito: 9045 resulta em 18 e, depois, em 9. Para um n positivo, equivale a 1 + (n-1) % 9, porque todo número deixa o mesmo resto ao ser dividido por 9 que a soma de seus dígitos.

A versão com strings ou a versão aritmética é melhor?

Ambos são O(d) e ambos estão corretos. A versão com string é mais curta de escrever em muitas linguagens, mas cria uma cópia dos dígitos. A versão aritmética usa O(1) de memória extra e mostra ao entrevistador que você sabe como % 10 e / 10 decompõem um número, algo que volta a aparecer em problemas de palíndromo e inversão de dígitos.

Python

def sumOfDigits(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

n = 9045

Esperado