Fácil 0 resolvidos 0% de aceitação

Número Feliz

Descubra se, somando repetidamente os quadrados dos dígitos de um número, você chega a 1.

O que você vai aprender

  • Calcular a soma dos quadrados dos dígitos
  • Detectar uma sequência que se repete com um conjunto ou dois ponteiros
  • Parar um laço por qualquer uma de duas condições

Problema

Ver original (inglês)

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

Exemplo 1
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.

Exemplo 2
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.