Project Euler #16 - Power digit sum

2¹⁵ = 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¹⁰⁰⁰?

출처: https://projecteuler.net/

큰 수의 곱셈은 karatsuba algorithm 을 통해 구했고 2 power 1000 은 divide and conquer algorithm 을 통해 시간 복잡도를 줄였습니다. multiply 메써드는 karatsuba algorithm 포스팅에서 확인하실 수 있습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
 
string solve(int n)
{
    if (n == 1)
        return "2";
    if (n % 2 == 1)
        return multiply(solve(n - 1), string("2"));
 
    return multiply(solve(n / 2), solve(n / 2));
}
 
int main()
{
    string str = solve(1000);
 
    int ret = 0;
    for (int i = 0; i < str.size(); i++)
        ret += (str[i] - '0');
 
    cout << ret << endl;
 
    system("pause");
    return 0;
}

multiply method is in karatsuba algorithm posting