Problem 16 : Power digit sum (5%)

link

Description

original

$2^{15} = 32768$ and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number $2^{1000}$?

간략해석

$2^{1000}$의 각 자릿수의 합을 구하시오.

Idea & Algorithm

naive idea

실제 계산 시간 복잡도는 얼마 안되지만, $2^{1000}$은 약 300자리이므로 오버플로우가 발생한다. 그렇기에 다음 문제를 위해서는 BigInteger를 지원하는 언어 또는 이를 구현해서 풀어야한다.

advanced idea

이 당시에는 배열로 간단하게 빅인티저를 구현해서 풀었다. 배열의 각 칸은 i번째 자릿수를 의미한다. 계속 2배씩 1000번 반복하여 풀었다.

python으로는 한 줄 코딩이 가능하다.

source code

#include <stdio.h>

int arr[500];

int main(){
    arr[0] = 1;
    for(int i = 0 ; i < 1000 ; i++){
        for(int j = 0 ; j < 500 ; j++){
            arr[j] *= 2;
        }
        for(int j = 0 ; j < 500 ; j++){
            if(arr[j]>9){
                arr[j+1] += arr[j]/10;
                arr[j] %= 10;
            }
        }
    }
    int sum = 0;
    for(int i = 0 ; i < 500 ; i++){
        sum += arr[i];
    }
    printf("%d\n",sum);
}

print(sum(map(int,str(2**1000))))

Problem 016