C++ Implementation of Problem 20
View source code here on GitHub!
Includes
Solution
-
uint64_t p0020()
-
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 20
3
4Problem:
5
6n! means n × (n − 1) × ... × 3 × 2 × 1
7
8For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
9and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
10
11Find the sum of the digits in the number 100!
12*/
13#ifndef EULER_P0020
14#define EULER_P0020
15#include <stdint.h>
16#include <iostream>
17#include <vector>
18#include "include/macros.hpp"
19
20
21uint64_t EMSCRIPTEN_KEEPALIVE p0020() {
22 std::vector<uint64_t> numbers(10, 0);
23 const uint64_t ten17 = 100000000000000000;
24 numbers[0] = 1;
25 for (uint8_t i = 2; i <= 100; i++) {
26 for (size_t j = 0; j < numbers.size(); j++)
27 numbers[j] *= i;
28 for (size_t j = 0; j < numbers.size() - 1; j++) {
29 if (numbers[j] > ten17) {
30 numbers[j + 1] += numbers[j] / ten17;
31 numbers[j] %= ten17;
32 }
33 }
34 }
35 uint64_t answer = 0;
36 uint64_t power = 1;
37 for (uint8_t i = 0; i < 18; i++) {
38 for (size_t j = 0; j < numbers.size(); j++)
39 answer += (numbers[j] / power) % 10;
40 power *= 10;
41 }
42 return answer;
43}
44
45PROGRAM_TAIL(p0020)
46#endif