Alle Herausforderungen
Einfach 0 gelöst 0% Erfolgsquote

Digit Sum of a Power of Two

Add up the decimal digits of 2 raised to the power n.

Das lernst du

  • Double a number stored as digits
  • Sum the digits of a large number
  • Handle the n = 0 case

Problem

Übersetzung anzeigen

Powers of two grow fast: 2^64 already has 20 digits and 2^2000 has over 600. Compute 2^n exactly and add up its decimal digits. Without big integers, keep the number as an array of digits and double it n times.

Implement digit_sum_power_of_two(n).

Input

n: The exponent.

Output

Return the sum of the decimal digits of 2^n.

Einschränkungen

0 ≤ n ≤ 2000

Beispiele

Beispiel 1
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 and 1 + 0 + 2 + 4 = 7.

Beispiel 2
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, so the digit sum is 1.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

2^n is 1 doubled n times.

Hinweis 2

Store digits with the lowest digit first so carries move toward the end of the array.

Hinweis 3

Add the digits only once the doubling is finished.

Erwartete Komplexität

O(n²) time, O(n) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.