Problema
Il n-esimo numero triangolare è 1 + 2 + … + n. Una formula permette di evitare cicli su input molto grandi. Il numero triangolare di 0 è 0.
Implementa triangular_number(n).
Input
n: Un intero non negativo.
Output
Restituisci 1 + 2 + … + n.
Vincoli
0 ≤ n ≤ 1.000.000.000. Il risultato rientra in un intero con segno a 64 bit.
Esempi
Input:
n = 10
Output atteso:
expected = 55
Input:
long long n = 10;
Output atteso:
long long expected = 55;
Input:
long n = 10;
Output atteso:
long expected = 55;
Spiegazione
1 + 2 + … + 10 = 55.
Input:
n = 0
Output atteso:
expected = 0
Input:
long long n = 0;
Output atteso:
long long expected = 0;
Input:
long n = 0;
Output atteso:
long expected = 0;
Spiegazione
Non ci sono numeri da sommare, quindi la somma è 0.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Cerca un pattern nelle somme cumulative invece di aggiungere ogni numero uno per uno.
Suggerimento 2
Usa la scorciatoia della progressione aritmetica basata primo e ultimo termine, così eviti il ciclo.
Suggerimento 3
Fai attenzione al caso 0 e assicurati che l’aritmetica resti entro i limiti dei 64 bit.
Complessità attesa
tempo O(1), spazio aggiuntivo O(1)