"""
Problem 20: https://projecteuler.net/problem=20

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!
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.8.3
@creat_time = 2022/5/8
'''

def solution1(n: int = 100) -> int:
    '''
    >>> print(solution1(10))
    27
    '''
    
    import math
    return sum(map(int, str(math.factorial(n))))

# ********************************************************

def largeNumProduct(numx, numy) -> str:
    '''
    >>> print(largeNumProduct(12,15))
    180
    >>> print(largeNumProduct(12,'150'))
    1800
    '''
    
    if int(numx) > int(numy): numy, numx = numx, numy
    numx = list(map(int, str(numx)))[::-1]
    numy = list(map(int, str(numy)))[::-1]
    
    xlen = len(numx)
    ylen = len(numy)
    
    pList = numy + [0] * (xlen)
    res = [0]*(xlen + ylen)
    
    addList = lambda alist,blist:[
              alist[i] + blist[i] for i in range(len(alist))]

    for i in range(xlen):
        tmp = [0]*(xlen + ylen)
        
        carry = 0
        for j in range(len(pList)):
            carry, tmp[j] = divmod(numx[i] * pList[j] + carry, 10)
        
        for r in range(i):
            tmp = [tmp.pop()] + tmp
        
        res = addList(res, tmp)
    
    carry = 0
    for i in range(len(res)):
        carry, res[i] = divmod(res[i] + carry, 10)
    
    return (''.join(map(str,res[::-1]))).lstrip('0')
        

def solution2(n: int = 100) -> int:
    '''
    >>> print(solution1(10))
    27
    '''
    
    from functools import reduce
    product = reduce(largeNumProduct, range(2, n+1))
        
    
    return sum(map(int, product))

# ********************************************************


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(solution1())
    # 648
    print(solution2())