Problem
Die n-te Dreieckszahl ist 1 + 2 + … + n. Eine Formel vermeidet das Durchlaufen großer Eingaben. Die 0-te Dreieckszahl ist 0.
Implementiere triangular_number(n).
Eingabe
n: Eine nichtnegative ganze Zahl.
Ausgabe
Gib 1 + 2 + … + n zurück.
Einschränkungen
0 ≤ n ≤ 1.000.000.000. Das Ergebnis passt in einen vorzeichenbehafteten 64-Bit-Integer.
Beispiele
Eingabe:
n = 10
Erwartete Ausgabe:
expected = 55
Eingabe:
long long n = 10;
Erwartete Ausgabe:
long long expected = 55;
Eingabe:
long n = 10;
Erwartete Ausgabe:
long expected = 55;
Erläuterung
1 + 2 + … + 10 = 55.
Eingabe:
n = 0
Erwartete Ausgabe:
expected = 0
Eingabe:
long long n = 0;
Erwartete Ausgabe:
long long expected = 0;
Eingabe:
long n = 0;
Erwartete Ausgabe:
long expected = 0;
Erläuterung
Keine Zahlen zum Addieren, daher ist die Summe 0.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Suche nach einem Muster in den laufenden Summen, statt jede Zahl einzeln zu addieren.
Hinweis 2
Nutze die Kurzform der arithmetischen Reihe mit erstem und letztem Term, so sparst du die Schleife.
Hinweis 3
Achte auf den 0-Fall und darauf, dass die Rechnung innerhalb von 64 Bit bleibt.
Erwartete Komplexität
Zeit O(1), zusätzlicher Speicher O(1)