Todos os desafios
Fácil 0 resolvidos 0% de aceitação

Número Abundante, Perfeito ou Deficiente

Classifique um número como abundante, perfeito ou deficiente pela soma dos seus divisores próprios.

O que você vai aprender

  • Somar os divisores próprios em tempo O(√n)
  • Evitar contar duas vezes um divisor que é raiz quadrada
  • Retornar um de três rótulos a partir de uma comparação

Problema

Ver original (inglês)

Os divisores próprios de n são os seus divisores positivos, exceto o próprio n. Compare a soma deles com n: se a soma for maior, o número é abundante; se for igual, o número é perfeito; e se for menor, o número é deficiente. Por exemplo, os divisores próprios de 12 são 1, 2, 3, 4 e 6, que somam 16, então 12 é abundante.

Implemente abundant_perfect_deficient(n).

n pode chegar a 10^12, então testar todos os números menores que n é lento demais. Os divisores aparecem em pares d e n / d, por isso basta testar d até √n.

Entrada

n: o número a ser classificado.

Saída

Retorne a string "abundant", "perfect" ou "deficient", em minúsculas. 1 não tem divisores próprios (soma 0), então é deficiente.

Restrições

1 ≤ n ≤ 10^12

Exemplos

Exemplo 1
Entrada:
n = 28

Saída esperada:
expected = "perfect"
Entrada:
long long n = 28;

Saída esperada:
std::string expected = "perfect";
Entrada:
long n = 28;

Saída esperada:
string expected = "perfect";

Explicação

Os divisores próprios 1 + 2 + 4 + 7 + 14 somam 28, então a resposta é "perfect".

Exemplo 2
Entrada:
n = 15

Saída esperada:
expected = "deficient"
Entrada:
long long n = 15;

Saída esperada:
std::string expected = "deficient";
Entrada:
long n = 15;

Saída esperada:
string expected = "deficient";

Explicação

Os divisores próprios 1 + 3 + 5 somam 9, que é menor que 15, então a resposta é "deficient".

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Se d divide n, então n / d também divide; faça o laço em d só enquanto d × d ≤ n.

Dica 2

Quando d × d = n, some d uma vez só, e não duas.

Dica 3

Lembre-se de deixar o próprio n fora da soma e trate n = 1 separadamente.

Complexidade esperada

tempo O(√n), espaço extra O(1)

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.