Project Euler #254: Sums of Digit Factorials

Question

Is there a better/efficient way of doing this?
Link: HackerRank | Project Euler #254. The time and space complexity increases exponentially. Any clues about how to improve the code or a change of approach would be very helpful.

# Enter your code here. Read input from STDIN. Print output to STDOUT
def factorial(num):
    result = 1
    for i in range(1, num+1):
        result *= i
    return result


def f(n):
    fact_table = [factorial(i) for i in range(10)]
    return sum([fact_table[int(i)] for i in str(n)])

def sf(n):
    return sum([int(i) for i in str(f(n))])


def g(i):
    n = 1
    sf_val = sf(n)
    while sf_val != i:
        n += 1
        sf_val = sf(n)
    return n

# print(g(48))


def sg(i):
    return sum([int(i) for i in str(g(i))])


# print(sg(3))

def solve(n, m):
    result = sum([sg(i) for i in range(1,n+1)])
    return result % m

# print(solve(3, 1000))



if __name__ == '__main__':
    result = []
    for i in range(int(input())):
        n, m = map(int, input().split())
        result.append(solve(n, m))
    for i in result:
        print(i)

maybe the question is more suited to: https://codereview.stackexchange.com/ — Mohammad, Jul 31 '21 at 16:30
You should create `fact_table` once, not every time you call `f()` — Barmar, Jul 31 '21 at 16:30
Agreeing with @Bamar, a technique called memoization is the poster child of factorial tables. Please see https://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python . — rajah9, Jul 31 '21 at 16:36

score -1 · Answer 1 · answered Mar 19 '22 at 17:56

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int fact[] = {1,1,2,6,24,120,720,5040,40320,362880};
int factorialSum(int value)
{
    int max=-1;
    int num;
    int sum=0;
    while(value!=0)
    {
        num = value%10;
        sum = sum + fact[num];
        value=value/10;
    }
    return sum;
}
int sumOfDigits(int value)
{
    int sum=0;
    while(value!=0)
    {
        sum = sum + value%10;
        value = value/10;
    }
    return sum;
}
int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
     int count=1;
     int g[100000];
     int sum=0;
     int len;
     int modulo[100000];
     scanf("%d",&len);
     int result[100];
     for(int x=0;x<len;x++)
     {
         scanf("%d %d",&g[x],&modulo[x]);
     }
     int temp;
     for(int i=0;i<len;i++)
     {
         for(int j=0;j<len;j++)
         {
             if(g[i]<g[j])
             {
                temp = g[i];
                g[i] = g[j];
                g[j] = temp;
                temp = modulo[i];
                modulo[i] = modulo[j];
                modulo[j] = temp;   
             }
         }
     }
     
     for(int x=0;x<len;x++)
     {
         int i=1;
         //sum=0;
         if(x!=0)
         {
             i = g[x-1]+1;
             sum=result[x-1];
         }
         //printf("%d",i);
         for(;i<=g[x];i++)
         {
             count=1;
             while(sumOfDigits(factorialSum(count++))!=i);
             count = count -1;
             sum = sum + sumOfDigits(count);
         }
         result[x]=sum;
    }
     for(int x=0;x<len;x++)
     {
         printf("%d\n",result[x]%modulo[x]);
     }
    return 0;
}

I hope this will be efficient. Still not accepted.

Project Euler #254: Sums of Digit Factorials

1 Answers1