Project Euler Solution 20
Problem Statement#
Find the sum of digits in 100!
n! means n ×(n-1) ×... ×3 ×2 ×1
For example, 10! = 10 ×9 ×... ×3 ×2 ×1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100!
Solution#
To solve this problem, one must know what is factorial and would be able to solve few of the previous problems. Try please..
Implementation#
#include <stdio.h>
int NUMBER = 100;int main(){ int index, val, num[3], t_prod[1000] = { 0 }, prod[1000] = { 0 }, f_prod[1000] = { 0 }; int pos, carry, no_dig_num, p, p_index, carry1, no_dig_prod, sum, t_dig_prod; prod[0] = 1; no_dig_prod = 1; int sum_dig; for (int i = 1; i <= NUMBER; i++) { val = i; while (val % 10 == 0) val = val / 10; if (val == 1) continue; index = 0; while (val != 0) { num[index] = val % 10; val = val / 10; index++; } no_dig_num = index; carry = 0; pos = 0; for (int i = 0; i < no_dig_num; i++) { p_index = 0; carry = 0; for (int j = 0; j < no_dig_prod; j++) { p = (prod[j] *num[i]) + carry; if (p < 10) { t_prod[p_index] = p; carry = 0; } if (p >= 10) { t_prod[p_index] = p % 10; p = p / 10; carry = p % 10; } p_index++; if (j == (no_dig_prod - 1) && carry != 0) { t_prod[p_index] = carry; p_index++; break; } } carry1 = 0; t_dig_prod = pos; int m; m = 0; for (int k = pos; k < pos + p_index; k++) { sum = f_prod[k] + t_prod[m] + carry1; if (sum < 10) { f_prod[t_dig_prod] = sum; carry1 = 0; } if (sum >= 10) { f_prod[t_dig_prod] = sum % 10; sum = sum / 10; carry1 = sum % 10; } t_dig_prod++; if (m == (p_index - 1) && carry1 != 0) { f_prod[t_dig_prod] = carry1; t_dig_prod++; break; } m++; if (m > (p_index - 1)) break; } pos++; } no_dig_prod = t_dig_prod; sum_dig = 0; for (int s = 0; s < no_dig_prod; s++) { sum_dig = sum_dig + f_prod[s]; prod[s] = f_prod[s]; f_prod[s] = 0; } } printf("sum :%d", sum_dig); return 0;}Sample Output#
