Problème
Le n-ième nombre triangulaire est 1 + 2 + … + n. Une formule permet d'éviter de boucler sur de très grandes valeurs de n. Le 0ᵉ nombre triangulaire est 0.
Implémentez triangular_number(n).
Entrée
n : Un entier non négatif.
Sortie
Retournez 1 + 2 + … + n.
Contraintes
0 ≤ n ≤ 1 000 000 000. Le résultat tient dans un entier signé de 64 bits.
Exemples
Entrée :
n = 10
Sortie attendue :
expected = 55
Entrée :
long long n = 10;
Sortie attendue :
long long expected = 55;
Entrée :
long n = 10;
Sortie attendue :
long expected = 55;
Explication
1 + 2 + … + 10 = 55.
Entrée :
n = 0
Sortie attendue :
expected = 0
Entrée :
long long n = 0;
Sortie attendue :
long long expected = 0;
Entrée :
long n = 0;
Sortie attendue :
long expected = 0;
Explication
Aucun nombre à additionner, donc la somme est 0.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Cherche un motif dans les sommes cumulées au lieu d’ajouter chaque nombre un par un.
Indice 2
Utilise le raccourci de la suite arithmétique basé sur le premier et le dernier terme, ce qui évite une boucle.
Indice 3
Fais attention au cas 0, et vérifie que tes calculs restent dans les limites du 64-bit.
Complexité attendue
temps O(1), espace supplémentaire O(1)