Problem 20 : Factorial digit sum (5%)

Description

original

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!

간략해석

100!의 각자리 수 합을 구하시오.

Idea & Algorithm

naive idea

BigInteger를 활용하여 구현하면 된다. 16번 문제에 풀이가 있으니 이를 참조하면 된다.

advanced idea

python도 마찬가지로 똑같이하면된다.

source code

#include <stdio.h>

int arr[500] = {1,};


int main(){
    for(int i = 1 ; i <= 100 ; i++){
        for(int j = 0 ; j < 500 ; j++){
            arr[j] *= i;
        }
        for(int j = 0 ; j < 499 ; j++){
            if(arr[j]>=10) arr[j+1] += arr[j]/10;
            arr[j] %= 10;
        }
    }
    int tot = 0;
    for(int i = 0 ; i < 500 ; i++){
        tot += arr[i];
    }
    printf("%d",tot);
}

print(sum(map(int,str(2**1000))))

Problem 020