C++ Implementation of Problem 16
View source code here on GitHub!
Includes
Solution
-
uint64_t p0016()
-
int main(int argc, char const *argv[])
Note
This function is only present in the Python test runner, or when compiling as a standalone program.
1/*
2Project Euler Problem 16
3
4Problem:
5
62**15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
7
8What is the sum of the digits of the number 2**1000?
9*/
10#ifndef EULER_P0016
11#define EULER_P0016
12#include <stdint.h>
13#include <iostream>
14#include <vector>
15#include "include/macros.hpp"
16
17
18uint64_t EMSCRIPTEN_KEEPALIVE p0016() {
19 std::vector<uint64_t> numbers(18, 0);
20 const uint64_t ten17 = 100000000000000000;
21 numbers[0] = 1;
22 for (uint16_t i = 0; i < 1000; i++) {
23 for (size_t j = 0; j < numbers.size(); j++)
24 numbers[j] *= 2;
25 for (size_t j = 0; j < numbers.size() - 1; j++)
26 if (numbers[j] > ten17) {
27 numbers[j + 1] += numbers[j] / ten17;
28 numbers[j] %= ten17;
29 }
30 }
31 uint64_t answer = 0;
32 uint64_t power = 1;
33 for (uint8_t i = 0; i < 18; i++) {
34 for (size_t j = 0; j < numbers.size(); j++)
35 answer += (numbers[j] / power) % 10;
36 power *= 10;
37 }
38 return answer;
39}
40
41PROGRAM_TAIL(p0016)
42#endif