All challenges
Easy 0 solved 0% acceptance

Digit Sum of a Power of Two

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

What you'll learn

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

Problem

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.

Constraints

0 ≤ n ≤ 2000

Examples

Example 1
Input:
n = 10

Expected output:
expected = 7
Input:
long long n = 10;

Expected output:
long long expected = 7;
Input:
long n = 10;

Expected output:
long expected = 7;

Explanation

2^10 = 1024 and 1 + 0 + 2 + 4 = 7.

Example 2
Input:
n = 0

Expected output:
expected = 1
Input:
long long n = 0;

Expected output:
long long expected = 1;
Input:
long n = 0;

Expected output:
long expected = 1;

Explanation

2^0 = 1, so the digit sum is 1.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

2^n is 1 doubled n times.

Hint 2

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

Hint 3

Add the digits only once the doubling is finished.

Expected complexity

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

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.