Compute Factorial Digit Sum: Find the sum of the digits in the n

  • 时间:2020-09-10 12:45:51
  • 分类:网络文摘
  • 阅读:123 次

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) —

推荐阅读:
How to Find Pivot Index of Array?  The Image Flood Fill Algorithm (C++)  How to Clone a Graph in C++/Java using Depth First Search Algori  The Unique Morse Code Words Algorithm  The Algorithm to Find Anagram Mappings between Two Arrays  How to Write More Readable Blog Posts  Due.com Review: It Really Is An Easy Way to Keep Track of Your I  Twitter Mishaps: The Infamous, The Insensitive, and the Unfunny  Standing Out from the Crowd: How to Get Your Content Noticed in   How to Leverage Social Media for Events to Achieve Your Goals 
评论列表
添加评论