Problem
Zweierpotenzen wachsen schnell: 2^64 hat schon 20 Stellen und 2^2000 mehr als 600. Berechne 2^n exakt und bilde die Quersumme. Ohne große Ganzzahlen speicherst du die Zahl als Array von Ziffern und verdoppelst sie n-mal.
Implementiere digit_sum_power_of_two(n).
Eingabe
n: Der Exponent.
Ausgabe
Gib die Quersumme von 2^n zurück.
Einschränkungen
0 ≤ n ≤ 2000
Beispiele
Eingabe:
n = 10
Erwartete Ausgabe:
expected = 7
Eingabe:
long long n = 10;
Erwartete Ausgabe:
long long expected = 7;
Eingabe:
long n = 10;
Erwartete Ausgabe:
long expected = 7;
Erläuterung
2^10 = 1024 und 1 + 0 + 2 + 4 = 7.
Eingabe:
n = 0
Erwartete Ausgabe:
expected = 1
Eingabe:
long long n = 0;
Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long n = 0;
Erwartete Ausgabe:
long expected = 1;
Erläuterung
2^0 = 1, die Quersumme ist also 1.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
2^n ist die 1, n-mal verdoppelt.
Hinweis 2
Speichere die Ziffern mit der niedrigsten zuerst, dann wandern Überträge zum Ende des Arrays.
Hinweis 3
Addiere die Ziffern erst, wenn das Verdoppeln fertig ist.
Erwartete Komplexität
Zeit O(n²), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.