Powerful digit sum | Project Euler | Problem #56
URL to the problem page: https://projecteuler.net/problem=56
A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?
A googol (10¹⁰⁰) is a massive number: one followed by one-hundred zeros; 100¹⁰⁰ is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?
#include <iostream>
using namespace std;
int main()
{
const int k = 1000;
int result[2][k], carry[2], number2[2] = { 0, 0 }, i, j, a, b, c, tmp, carry_4, number[k], biggest = 0;
for (a = 0; a < 99; a++) {
for (j = 1; j >= 0; j--) {
if (number2[j] == 9) {
number2[j] = 0;
}
else if (number2[j] < 9) {
number2[j]++;
break;
}
}
for (j = 0; j < 99; j++) {
for (i = 0; i < k; i++) {
number[i] = 0;
}
number[k - 1] = number2[1];
number[k - 2] = number2[0];
for (c = 0; c < j; c++) {
for (i = 0; i < 2; i++) {
carry[i] = 0;
for (b = 0; b < k; b++) {
result[i][b] = 0;
}
}
for (i = k - 1; i >= 0; i--) {
result[1][i] = ((number[i] * number2[1]) + carry[0]) % 10;
carry[0] = ((number[i] * number2[1]) + carry[0]) / 10;
result[0][i] = ((number[i] * number2[0]) + carry[1]) % 10;
carry[1] = ((number[i] * number2[0]) + carry[1]) / 10;
}
number[k - 1] = result[1][k - 1];
number[k - 2] = (result[1][k - 2] + result[0][k - 1]) % 10;
carry_4 = (result[1][k - 2] + result[0][k - 1]) / 10;
for (i = k - 3; i >= 0; i--) {
number[i] = (result[1][i] + result[0][i + 1] + carry_4) % 10;
carry_4 = (result[1][i] + result[0][i + 1] + carry_4) / 10;
}
}
tmp = 0;
for (i = k - 1; i >= 0; i--) {
tmp += number[i];
}
if (tmp > biggest) {
biggest = tmp;
}
}
}
cout << "Maximum digital sum, considering natural numbers of the form, a^b, where a, b < 100 is = " << biggest << endl;
return 0;
}
Comments
Post a Comment