Armstrong Number
Um número inteiro positivo é um número de Armstrong quando é igual à soma de seus próprios dígitos, cada um elevado à potência correspondente à quantidade de dígitos que ele tem. 153 tem três dígitos e 1^3 + 5^3 + 3^3 = 153, portanto, é um deles. Escreva uma função que receba n e retorne true se ele for um número de Armstrong e false caso contrário.
Função
- ninteger
- o número inteiro positivo a ser testado
- Retornaboolean
- verdadeiro quando n é igual à soma de seus dígitos, cada um elevado ao número de dígitos
Restrições
1 ≤ n ≤ 109
Exemplos
- Entrada
- n = 153
- Saída
- true
- Explicação
153tem 3 dígitos, então cada dígito é elevado ao cubo:1 + 125 + 27 = 153. A soma resulta no próprio número, então a resposta étrue.
- Entrada
- n = 10
- Saída
- false
- Explicação
10tem 2 dígitos, então cada dígito é elevado ao quadrado:1 + 0 = 1, que não é10. A resposta éfalse.
- Entrada
- n = 9474
- Saída
- true
- Explicação
- Com 4 dígitos, a potência é 4:
6561 + 256 + 2401 + 256 = 9474, o próprio número, então a resposta étrue.
+31 testes ocultos ao enviar
Para ir além
Apenas 31 números de Armstrong estão entre 1 e 10^9. Você consegue listar todos eles sem testar um bilhão de números, um por um?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Antes de elevar um dígito a uma potência, você precisa do expoente. Quantos dígitos
ntem e como você pode descobrir isso usando aritmética?n % 10é o último dígito, e a divisão inteira por 10 o remove. Repita até não sobrar nada: isso percorre todos os dígitos, e o número de etapas é o expoentek.Conte os dígitos em uma única passagem. Depois, extraia-os novamente, some cada dígito elevado à potência
ka um total de 64 bits e retorne se o total é igual aonoriginal.
Solução
A definição é o algoritmo: descubra quantos dígitos n tem, eleve cada dígito a essa potência, some os resultados e compare com n. As armadilhas estão nos números. O expoente é a quantidade de dígitos desse n específico, não um 3 fixo, e a soma pode ultrapassar um inteiro de 32 bits: para 999999999, ela é 9 × 9^9 = 3486784401.
Leia os dígitos da string
Intuição
A representação decimal de n fornece as duas coisas de que você precisa. Seu comprimento é o expoente k, e seus caracteres são os dígitos. Para 9474, a representação tem 4 caracteres, então você soma 9^4 + 4^4 + 7^4 + 4^4.
Converta cada caractere de volta em seu dígito, eleve-o à potência k e some-o a um total acumulado. n é um número de Armstrong exatamente quando o total final é igual a n.
Mantenha o total em um inteiro de 64 bits. n cabe em 32 bits, mas a soma não precisa caber: 999999999 resulta em 3486784401, acima do limite de 32 bits de 2147483647. Uma potência calculada com um loop de k multiplicações custa k etapas por dígito, então a verificação é O(k²), com k aproximadamente igual a log n. Neste caso, são no máximo 100 multiplicações, e a representação em string ocupa k caracteres de memória.
Algoritmo
- Converta
nem sua representação decimal como string e definakcomo seu comprimento. - Defina
totalcomo um inteiro de 64 bits com valor0. - Para cada caractere, converta-o em seu dígito
de somed^katotal, multiplicando números inteiros em vez de chamar uma função de potência de ponto flutuante. - Retorne se
totalé igual an.
def isArmstrong(n):
digits = str(n)
k = len(digits)
total = 0
for ch in digits:
total += int(ch) ** k
return total == nSepare os dígitos e consulte suas potências
Intuição
A aritmética sozinha faz o mesmo trabalho sem uma string. m % 10 é o último dígito de m e a divisão inteira por 10 o remove; portanto, um loop que divide por 10 até não restar nada conta os dígitos. 9474 se torna 947, 94, 9, 0: quatro etapas, então k = 4.
Existem apenas dez dígitos, então monte uma tabela powers[d] = d^k para d de 0 a 9 antes de somar qualquer coisa. Cada dígito passa a exigir apenas uma consulta, em vez de k multiplicações. A verificação passa a levar O(log n) de tempo, e a tabela tem tamanho fixo de dez, o que corresponde a O(1) de espaço.
O segundo loop separa os dígitos novamente e adiciona powers[m % 10] ao total. Cada termo é zero ou positivo, então o total nunca diminui e, assim que ultrapassa n, a resposta é false. Para 999999999, isso acontece após três dígitos, em 3 × 387420489 = 1162261467. A tabela ainda precisa de 64 bits, porque n = 10^9 tem dez dígitos e 9^10 = 3486784401.
Algoritmo
- Conte os dígitos de
ndividindo uma cópia por 10 até ela chegar a 0; chame essa contagem dek. - Preencha
powers[d] = d^kpara cada dígitodde 0 a 9, usando inteiros de 64 bits. - Divida novamente uma cópia nova de
npor 10, adicionandopowers[m % 10]atotala cada etapa. - Se
totalultrapassarn, retornefalseimediatamente. - Após o último dígito, retorne se
totalé igual an.
def isArmstrong(n):
# Count the digits: k is the exponent.
k = 0
m = n
while m > 0:
k += 1
m //= 10
# powers[d] = d^k for the ten possible digits.
powers = [d ** k for d in range(10)]
total = 0
m = n
while m > 0:
total += powers[m % 10]
if total > n:
return False # the total only grows
m //= 10
return total == n
Armadilhas e casos extremos
A fórmula é curta, então os bugs vêm dos números ao redor dela.
- Um expoente fixo de 3. Ele aceita
153e370, mas rejeita9474, e rejeita todo número de um dígito acima de 1, já que7^3 = 343. - Uma soma de 32 bits.
999999999resulta em3486784401, e a entrada da tabela9^10é o mesmo número. Em C, esse overflow é um comportamento indefinido; Java e C# retornam um número negativo, e uma compilação de depuração do Rust entra em pânico. Uselong,long longoui64. - Potências de ponto flutuante.
powem C eMath.powem Java retornam umdouble. Alguns ambientes de execução de C já retornaram um valor um pouco abaixo de um número inteiro, como24.999...para5^2, que uma conversão de tipo trunca para24. Em vez disso, multiplique números inteiros em um loop. - Comparação com o valor errado. Os loops dos dígitos dividem
naté chegar a 0, então trabalhe com uma cópia e compare o total com o valor original. - Notação científica. Em R,
as.character(1e9)é"1e+09", com cinco caracteres, então uma solução em R baseada em strings formata comsprintf("%.0f", n).
Perguntas frequentes4
O que é um número de Armstrong?
Um número de Armstrong, também chamado de número narcisista, é igual à soma de seus próprios dígitos, cada um elevado à potência correspondente à quantidade de dígitos. 153 é um deles porque 1^3 + 5^3 + 3^3 = 153, e 9474 é um deles porque 9^4 + 4^4 + 7^4 + 4^4 = 9474. Todo número de um dígito se qualifica, pois d^1 = d.
Quantos números de Armstrong existem?
Na base 10, há exatamente 88 números positivos iguais à soma das potências de seus dígitos, e o maior tem 39 dígitos. A lista é finita porque um número com k dígitos é pelo menos 10^(k-1), enquanto a soma das potências de seus dígitos é no máximo k × 9^k, e, a partir de 61 dígitos, a soma nunca consegue alcançar o número. Entre 1 e 10^9, há 31.
Por que a verificação de número de Armstrong precisa de um inteiro de 64 bits?
A entrada cabe em 32 bits, mas a soma dos dígitos elevados a uma potência pode ser várias vezes maior que o número. 999999999 resulta em 9 × 9^9 = 3486784401, acima de 2^31-1 = 2147483647. Um total de 32 bits transborda nesse caso, então mantenha o total e as potências em um tipo de 64 bits.
Qual é a complexidade de tempo para verificar se um número é um número de Armstrong?
n tem cerca de log n dígitos, no máximo 10 aqui. Remover os dígitos e consultar cada potência em uma tabela de dez elementos leva O(log n) tempo e O(1) espaço. Recalcular d^k com um laço para cada dígito torna a complexidade O(log² n), ainda rápida para esse tamanho.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def isArmstrong(n):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
n = 153
Esperado
true