Tous les défis
Facile 0 résolus 0 % de réussite

Nombre abondant, parfait ou déficient

Classez un nombre comme abondant, parfait ou déficient d'après la somme de ses diviseurs stricts.

Ce que vous allez apprendre

  • Additionner les diviseurs stricts en temps O(√n)
  • Éviter de compter deux fois un diviseur égal à la racine carrée
  • Renvoyer l'une de trois étiquettes selon une comparaison

Problème

Les diviseurs stricts de n sont ses diviseurs positifs autres que n lui-même. Comparez leur somme à n. Si la somme est plus grande, le nombre est abondant. Si elle est égale, le nombre est parfait. Si elle est plus petite, le nombre est déficient. Par exemple, les diviseurs stricts de 12 sont 1, 2, 3, 4 et 6, dont la somme vaut 16, donc 12 est abondant.

Implémentez abundant_perfect_deficient(n).

n peut atteindre 10^12, il est donc beaucoup trop lent de tester tous les nombres inférieurs à n. Les diviseurs vont par paires d et n / d, il suffit donc d'essayer les d jusqu'à √n.

Entrée

n : le nombre à classer.

Sortie

Renvoyez la chaîne "abundant", "perfect" ou "deficient", en minuscules. 1 n'a aucun diviseur strict (somme 0), il est donc déficient.

Contraintes

1 ≤ n ≤ 10^12

Exemples

Exemple 1
Entrée :
n = 28

Sortie attendue :
expected = "perfect"
Entrée :
long long n = 28;

Sortie attendue :
std::string expected = "perfect";
Entrée :
long n = 28;

Sortie attendue :
string expected = "perfect";

Explication

Les diviseurs stricts 1 + 2 + 4 + 7 + 14 donnent 28, donc la réponse est "perfect".

Exemple 2
Entrée :
n = 15

Sortie attendue :
expected = "deficient"
Entrée :
long long n = 15;

Sortie attendue :
std::string expected = "deficient";
Entrée :
long n = 15;

Sortie attendue :
string expected = "deficient";

Explication

Les diviseurs stricts 1 + 3 + 5 donnent 9, ce qui est inférieur à 15, donc la réponse est "deficient".

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

Si d divise n, alors n / d aussi, donc ne faites varier d que tant que d × d ≤ n.

Indice 2

Quand d × d = n, ajoutez d une seule fois, pas deux.

Indice 3

Pensez à exclure n lui-même de la somme, et traitez n = 1 à part.

Complexité attendue

temps O(√n), espace supplémentaire O(1)

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.