Happy Number
Comece com um inteiro positivo n e substitua-o pela soma dos quadrados de seus dígitos, repetidamente. Por exemplo, 12 se torna 1² + 2² = 5. Se esse processo chegar a 1, n é um número feliz; caso contrário, ele entra em um ciclo infinito de números que nunca incluem 1. Retorne true se n for feliz e false se não for.
Função
- ninteger
- o número inteiro positivo a ser testado
- Retornaboolean
- verdadeiro se a repetição da soma dos quadrados dos dígitos chegar a 1, falso se entrar em um loop infinito
Restrições
1 ≤ n ≤ 231-1
Exemplos
- Entrada
- n = 7
- Saída
- true
- Explicação
- 7 se torna 49, depois 4² + 9² = 97, depois 130, depois 10 e, então, 1. O processo chega a
1, então 7 é feliz.
- Entrada
- n = 2
- Saída
- false
- Explicação
- 2 se torna 4, 16, 37, 58, 89, 145, 42, 20 e então 4 novamente. A partir daí, os mesmos oito números se repetem para sempre e nunca chegam a
1.
- Entrada
- n = 100
- Saída
- true
- Explicação
- 1² + 0² + 0² = 1, então 100 chega a
1após uma etapa.
+16 testes ocultos ao enviar
Para ir além
Como você contaria rapidamente os números felizes de 1 a 10^6, reutilizando as respostas para números abaixo de 1000 em vez de percorrer cada número inicial do zero?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Tente algumas sequências iniciais manualmente. 7 chega a 1 em cinco etapas, enquanto 2 volta a 4 depois de oito etapas. O que isso indica quando um número volta?
Cada valor depende apenas do anterior, então, quando um número se repete, todo o trecho depois dele se repete para sempre. A pergunta passa a ser: o percurso chega a 1 antes de chegar a um número que já viu?
Mantenha um conjunto dos números que você já visitou e pare ao chegar a 1 ou ao encontrar uma repetição. Para usar memória constante, execute dois percursos a partir de
n, um dando um passo por rodada e o outro, dois; eles só podem se encontrar dentro de um ciclo.
Solução
A sequência nunca pode divergir para o infinito. Um número com 10 dígitos mapeia para, no máximo, 10 × 81 = 810, e um número abaixo de 1000 mapeia para, no máximo, 3 × 81 = 243; portanto, após uma etapa, a sequência permanece entre menos de 1000 valores e precisa chegar a 1 ou repetir um número. Isso transforma o problema em detecção de ciclos: lembre-se do que você já viu ou execute um percurso lento e outro rápido para ver se eles se encontram.
Lembre-se de todos os números que você viu
Intuição
Percorra a sequência e mantenha cada número em um conjunto hash. Antes de avançar de um número, verifique se ele já está no conjunto. Para 2, o conjunto é preenchido com 2, 4, 16, 37, 58, 89, 145, 42 e 20, e o próximo valor é 4, que já está nele: o percurso fechou um ciclo sem encontrar 1, então 2 não é feliz. Chegar a 1 encerra o percurso com true.
Isso está correto porque o próximo número depende apenas do atual. Quando um número aparece novamente, tudo o que vem depois se repete exatamente, então nenhum número novo pode aparecer, e 1 nunca aparecerá.
O percurso é curto. O primeiro passo lê os O(log n) dígitos de n, e cada valor posterior é menor que 1000, onde nenhum percurso visita mais de 20 números diferentes antes de chegar a 1 ou se repetir. O conjunto armazena esses números. O código C usa um array de flags com 1000 posições como conjunto e começa a registrar após o primeiro passo, quando todos os valores são menores que 1000.
Algoritmo
- Crie um conjunto hash vazio
seen. - Enquanto
nnão for 1, retornefalsesenestiver emseen. - Caso contrário, adicione
naseene substituanpela soma dos quadrados de seus dígitos. - Quando o loop terminar,
nserá 1: retornetrue.
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
seen = set()
while n != 1:
if n in seen:
return False # back at an earlier number: a loop without 1
seen.add(n)
n = digitSquareSum(n)
return TrueAndarilhos rápidos e lentos (detecção de ciclos de Floyd)
Intuição
Pense em cada número como um nó com uma seta, apontando para a soma dos quadrados de seus dígitos. Seguir as setas a partir de n leva a 1, cuja seta aponta de volta para 1, ou encontra um ciclo. Essa é a estrutura de uma lista encadeada que pode conter um ciclo, e o algoritmo de Floyd detecta um ciclo sem armazenar nada: slow avança um passo por rodada e fast avança dois.
Se o ciclo não contiver 1, os dois percursos acabam dando voltas nele, e a cada rodada fast ganha um passo em relação a slow, então a distância diminui em um até que eles estejam no mesmo número. Para 2, eles se encontram em 42 após sete rodadas. Se o percurso chegar a 1, fast chega primeiro e permanece lá, porque a soma para 1 é 1. Portanto, pare quando fast for 1 ou os percursos se encontrarem, e responda se fast é 1.
Para 7, slow percorre 7, 49, 97, enquanto fast percorre 49, 130, 1, e o ciclo termina com fast em 1. O número de rodadas é, no máximo, um pequeno múltiplo do comprimento do percurso, então o tempo é equivalente ao da versão com conjunto, e a memória usada é de dois inteiros.
Algoritmo
- Escreva uma função auxiliar que retorne a soma dos quadrados dos dígitos de um número.
- Defina
slow = ne definafastcomo o número uma etapa apósn. - Enquanto
fastnão for 1 eslowfor diferente defast, avanceslowuma etapa efastduas etapas. - Retorne se
fasté 1.
def digitSquareSum(n):
total = 0
while n > 0:
digit = n % 10
total += digit * digit
n //= 10
return total
def isHappy(n):
slow = n
fast = digitSquareSum(n)
# fast moves two steps for every step of slow; they meet only inside a loop.
while fast != 1 and slow != fast:
slow = digitSquareSum(slow)
fast = digitSquareSum(digitSquareSum(fast))
return fast == 1
Armadilhas e casos extremos
A aritmética dos dígitos é simples. A maioria dos erros está em quando o loop para.
- Continuar o loop até que o valor seja 1, sem nenhuma outra condição de saída. Para 2, esse loop nunca termina.
- Começar
slowefastno mesmo número e testarslow != fastantes do primeiro movimento. O loop nunca é executado, e 7 acaba sendo classificado como infeliz. Comecefastum passo à frente ou mova ambos antes da primeira comparação. - Retornar
slow == 1na versão de Floyd.fastchega a 1 primeiro e o loop para imediatamente, enquantoslowainda pode estar em 97. - Somar os dígitos em vez de seus quadrados, ou elevar o número inteiro ao quadrado. Para 12, o próximo valor é
1² + 2² = 5, não 3 nem 144. - Declarar
ninfeliz sempre que os ponteiros se encontram. 1 mapeia para si mesmo, então os ponteiros também se encontram em 1; verifique onde eles se encontraram ou pare assim quefastfor 1.
Perguntas frequentes4
Por que o processo sempre chega a 1 ou a um loop?
Um número com d dígitos mapeia para no máximo 81 × d, então números grandes diminuem rapidamente: qualquer número inicial até 2^31-1 fica abaixo de 1000 após uma etapa, e um número abaixo de 1000 mapeia para no máximo 243. A sequência fica presa entre menos de 1000 valores, então necessariamente revisita um deles e, a partir daí, entra em um ciclo. 1 é o único número que mapeia para si mesmo.
Qual é a complexidade temporal de Happy Number?
A primeira etapa lê os dígitos de n, em quantidade O(log n). Todos os valores posteriores são menores que 1000, e a sequência se repete em no máximo 20 números, então o tempo total é O(log n). A versão com conjunto hash armazena os números visitados; a versão de Floyd usa espaço O(1).
Por que todos os números infelizes acabam em 4?
Verificar todos os números abaixo de 1000 mostra exatamente um ciclo que não passa por 1: 4, 16, 37, 58, 89, 145, 42, 20 e de volta a 4. Como todo início cai abaixo de 1000, todo número infeliz acaba caindo nele. Uma solução pode parar assim que encontrar 4, mas isso depende de um fato que você teria que justificar em uma entrevista; o conjunto e o método de Floyd não exigem esse conhecimento.
Qual é a relação entre Número Feliz e Ciclo em Lista Ligada?
Ambos perguntam se seguir uma seta a partir de cada item alguma vez retorna a um item já visitado. No Happy Number, a seta é a soma dos quadrados dos dígitos; em uma lista encadeada, é o ponteiro para o próximo item. É por isso que os ponteiros rápido e lento de Floyd resolvem ambos com memória constante.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def isHappy(n):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
n = 7
Esperado
true