Problema
Comece com um inteiro positivo e troque-o pela soma dos quadrados dos seus dígitos. Repita o processo. Se em algum momento o número virar 1, o número inicial é feliz. Caso contrário, o processo entra em um ciclo que nunca passa pelo 1, e o número é infeliz. Por exemplo, 7 → 49 → 97 → 130 → 10 → 1, então 7 é feliz.
Implemente happy_number(n).
Você vai precisar de um jeito de perceber que a sequência começou a se repetir, para que o laço também pare nos números infelizes.
Entrada
n: o número inicial.
Saída
Retorne true se o processo chegar a 1, e false caso contrário. O próprio número 1 é feliz.
Restrições
1 ≤ n ≤ 10^9
Exemplos
Entrada:
n = 19
Saída esperada:
expected = True
Entrada:
long long n = 19;
Saída esperada:
bool expected = true;
Entrada:
long n = 19;
Saída esperada:
bool expected = true;
Explicação
1² + 9² = 82, depois 8² + 2² = 68, depois 6² + 8² = 100, depois 1² + 0² + 0² = 1, então 19 é feliz: true.
Entrada:
n = 4
Saída esperada:
expected = False
Entrada:
long long n = 4;
Saída esperada:
bool expected = false;
Entrada:
long n = 4;
Saída esperada:
bool expected = false;
Explicação
4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 se repete sem nunca chegar a 1, então a resposta é false.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Escreva uma função auxiliar que leve um número à soma dos quadrados dos seus dígitos.
Dica 2
Um número infeliz repete um valor que já produziu antes; guarde os valores que você já viu.
Dica 3
A sequência cai abaixo de algumas centenas muito rápido, então o conjunto continua pequeno.
Complexidade esperada
O(log n) passos por número, espaço extra O(1) com dois ponteiros
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.