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!
Algorithm to Compute Factorial Digit Sum
Since the factorial could be very large, we need to use an array (or hashmap) to store the digits of the answer. However, in some programming language, large values can be stored e.g. BigInteger in Java or Python.
Similar to Digit factorials: Find the Sum of All the Curious Numbers, we will compute the factorial and store the value in a dictionary.
Then the digits (values of the dictionary) are iterated and sum is obtained via the Array.reduce() function.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | let arr = { 0: 1 }; for (let i = 2; i <= 100; ++i) { // multiply by value i Object.keys(arr).map(x => { arr[x] *= i; }); let c = Math.floor(arr[0] / 10); let j = 1; arr[0] %= 10; // higest position of the value const maxKey = Math.max(...Object.keys(arr)); while ((c > 0) || (j <= maxKey)) { if (typeof arr[j] === 'undefined') { arr[j] = c; } else { arr[j] = arr[j] + c; } // carry over c = Math.floor(arr[j] / 10); arr[j] %= 10; j ++; } } // sum up all the digits of the answer console.log(Object.values(arr).reduce((a, b) => a + b)); |
let arr = {
0: 1
};
for (let i = 2; i <= 100; ++i) {
// multiply by value i
Object.keys(arr).map(x => {
arr[x] *= i;
});
let c = Math.floor(arr[0] / 10);
let j = 1;
arr[0] %= 10;
// higest position of the value
const maxKey = Math.max(...Object.keys(arr));
while ((c > 0) || (j <= maxKey)) {
if (typeof arr[j] === 'undefined') {
arr[j] = c;
} else {
arr[j] = arr[j] + c;
}
// carry over
c = Math.floor(arr[j] / 10);
arr[j] %= 10;
j ++;
}
}
// sum up all the digits of the answer
console.log(Object.values(arr).reduce((a, b) => a + b));–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
296 wordsloading...
Last Post: Compute the Maximum Integer Right Triangles Solutions
Next Post: How many different ways can £2 be made using any number of coins? (Depth First Search and Dynamic Programming)
