Project Euler #254: Sums of Digit Factorials

Sort by

recency

|

199 Discussions

|

  • + 0 comments

    IN JAVA BY: TANUSHREE SARKAR

    import java.util.Scanner;
    
    public class Solution {
        public static int f(int num) {
            int fact = num;
            if (num == 0) {
                fact = 1;
            } else {
                for (int i = num - 1; i > 0; --i) {
                    fact = fact * i;
                }
            }
            return fact;
        }
    
        public static int fn(int n) {
            int sum_f = 0;
            String temp = String.valueOf(n);
            for (int i = 0; i < temp.length(); ++i) {
                int conv_i = temp.charAt(i) - '0';
                sum_f += f(conv_i);
            }
            return sum_f;
        }
    
        public static int sfn(int num) {
            int sum_fn = 0;
            int sum_f = fn(num);
            String temp = String.valueOf(sum_f);
            for (int i = 0; i < temp.length(); ++i) {
                int conv_i = temp.charAt(i) - '0';
                sum_fn += conv_i;
            }
            return sum_fn;
        }
    
        public static int gi(int num) {
            int sum_fn;
            int i = 0;
            while (true) {
                ++i;
                sum_fn = sfn(i);
                if (num == sum_fn) {
                    break;
                }
            }
            return i;
        }
    
        public static int sgi(int num) {
            int sum_gi = 0;
            for (int i = 1; i <= num; ++i) {
                int temp = gi(i);
                if (temp < 10) {
                    sum_gi += temp;
                } else {
                    String s_temp = String.valueOf(temp);
                    for (int j = 0; j < s_temp.length(); ++j) {
                        int conv_i = s_temp.charAt(j) - '0';
                        sum_gi += conv_i;
                    }
                }
            }
            return sum_gi;
        }
    
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int q = scanner.nextInt();
            for (int i = 0; i < q; ++i) {
                int n = scanner.nextInt();
                int m = scanner.nextInt(); // not used in the code
                System.out.println(sgi(n));
            }
        }
    }
    
  • + 0 comments
    import sys
    import math
    import time
    import timeit
    from decimal import Decimal
    def f(n):
        #return sum([int(i) * f(str(int(i) - 1)) if int(i) > 1 else 1 for i in n])
        return sum(math.factorial(int(i)) for i in n)
    def sf(n):
        return sum(int(i) for i in str(f(n)))
    def sg(n):
        dfg = DefindG(n)
        return sum(int(d) for d in str(dfg))
    def ms(n):
        d_sg = {1: 1, 2: 2, 3: 5, 4: 6, 5: 7, 6: 3, 7: 4, 8: 5, 9: 6, 10: 7,
                11: 8, 12: 8, 13: 9, 14: 13, 15: 9, 16: 10, 17: 11, 18: 13,
                19: 14, 20: 15, 21: 16, 22: 17, 23: 18, 24: 13, 25: 14, 26: 15,
                27: 9, 28: 10, 29: 11, 30: 12, 31: 13, 32: 14, 33: 12, 34: 13,
                35: 14, 36: 15, 37: 19, 38: 28, 39: 24, 40: 25, 41: 37, 42: 31,
                43: 32, 44: 45, 45: 46, 46: 50, 47: 66, 48: 67, 49: 71, 50: 84,
                51: 89, 52: 90, 53: 114, 54: 118, 55: 134, 56: 154, 57: 158, 58: 193,
                59: 231, 60: 235, 61: 247, 62: 317, 63: 321, 64: 545, 65: 843, 66: 1052,
                67: 1339, 68: 1574, 69: 1846, 70: 2035, 71: 2294, 72: 2566, 73: 5035,
                74: 7578, 75: 9997, 76: 12529, 77: 15009, 78: 17415, 79: 19912, 80: 22416,
                81: 24933, 82: 49686, 83: 74498, 84: 99334, 85: 124135, 86: 148899,
                87: 173672, 88: 198536, 89: 223324, 90: 248145, 91: 496173, 92: 744212,
                93: 992162, 94: 1240190, 95: 1488229, 96: 1736179, 97: 1984255,
                98: 2232318, 99: 2480268, 100: 4960419, 101: 7440581, 102: 9920765,
                103: 12400916, 104: 14881015, 105: 17361186, 106: 19841385, 107: 22321571}
        #return sum(sg(i) for i in range(1, n + 1))
        return sum(d_sg[i] for i in range(1, n + 1))
    def StartFrom(n):  # this function returns The first possible compilation group for (n)
        r = int()
        for nf in range(9, 0, -1):
            if n >= nf:
                r = int(n / nf)
                m = f"{r * str(nf)}"
                m = f"{(n - (sum(int(j) for j in m)))}{r * str(nf)}"
                return int(m)
    def SumIntegers(n):
        return sum(int(i) for i in str(n))
    def Findf(n):  # 389,999,999,999 EX SUM = 101 3000*F9 +1000*F8 +
        temp = n
        qum = ''  # fac 9
        fac = (1, 2, 6, 24, 120, 720, 5040, 40320, 362880)  # factorials from 1-9
        for i in range(1, 10):
            s = 0
            m = (10 - i)
            divf = int(n / fac[m - 1])
            if divf > 0:
                qum += divf * str(m)  # other choice F(m)
                n = int(n % fac[m - 1])
        return qum[::-1]  # , int(qum[::-1])
    def fastsums(n, i, note):
        end = False
        lenthI = int(math.log10(i))  # len(str(i)) - 1
        lNum = int(str(i)[-1])
        if SumIntegers(i + 1) == n: # and '0' not in str(i + 9)
            i = i + 1
            note = int(math.log10(i))
            #print(i, 'DER', 9, note)
        elif SumIntegers(i + 9) == n: # and '0' not in str(i + 9)
            i = i + 9
            note = int(math.log10(i))
            #print(i, 'DER', 9, note)
        elif lNum > 1:
            checked = False
            for z in range(0, lenthI):
                surplus = int(f'{lNum}{z * "0"}{9 - lNum}')
                if SumIntegers(i + surplus) == n: # and '0' not in str(i + surplus)
                    i = i + surplus
                    note = int(str(surplus).count('0'))
                    if note != 0 and lNum < 9:
                        note = note + 1
                    if note == 0:
                        note = int(math.log10(i))
                    #print(i, 'SUR', surplus, note)
                    checked = True
                    break
            if checked is False:
                for ez in range(9, int((lenthI + 3) * '9')):
                    if SumIntegers(i + ez) == n: # '0' not in str(i + ez) and
                        i = i + ez
                        note = int(str(ez).count('0'))
                        lez = int(str(ez)[-1])
                        if note != 0 and lez < 9:
                            note = note + 1
                        if note == 0:
                            note = int(math.log10(ez))
                        #print(i, 'EZ', ez, note)
                        break
        elif lNum == 1 or lNum == 0:
            checked = False
            if lNum == 1 and i > 100:
                lNum2 = int(str(i)[:lenthI - 2:-1])
                strlNum2 = str(i)[:lenthI - 2:-1]
                for z in range(0, note):  # lenthI
                    surplus = int(f'{lNum2}{z * "0"}{9 - int(strlNum2[1])}{9 - int(strlNum2[0])}')
                    if SumIntegers(i + surplus) == n and surplus != 0:
                        i = i + surplus
                        note = int(str(surplus).count('0'))
                        checked = True
                        #print(i, 'NUM1', surplus, note)
                        break
            if checked is False or lNum == 0 :
                if str(i).count('1') != len(str(i)):
                    for ez in range(9, int((lenthI + 3) * '9')):
                        if SumIntegers(i + ez) == n: #'0' not in str(i + ez) and
                            i = i + ez
                            note = int(str(ez).count('0'))
                            lez = int(str(ez)[-1])
                            if note != 0 and lez < 9:
                                note = note + 1
                            if note == 0:
                                note = int(math.log10(ez))
                            #print(i, 'EZ1', ez, note)
                            break
                else:
                    end = True
        return i, note, end
    def DefindG(n):
        if n == 1:return '1'
        if n == 2:return '2'
        if n == 3:return '5'
        #if n == 9:return '6'
        resultat = str()
        h = StartFrom(n)
        note = int(math.log10(h))
        rs = 0
        start_time = time.time()
        seconds = 5
        count = 0
        while True:
            count += 1
            current_time = time.time()
            elapsed_time = current_time - start_time
            q = Findf(h)
            #print(q,    h)
            countq = len(q)
            #print(countq)
            #counqq = ''.join(q.split('9'))
            #print(q ,2355679)
            if rs == 0:
                rs = len(q) + 999
            # print('\r', h, sf(q), end='', flush=True)
            if sf(q) == n and countq <= rs:
                if countq < rs:
                    resultat = q
                    rs = countq
                else:
                    #tttsr = ''.join(resultat.split('9'))
                    if int(q[:100]) < int(resultat[:100]):
                        resultat = q
                        rs = countq
            res, note, end = fastsums(n, h, note) #here is the problem 5 most returns 122 AND ITS LIMIT IS 50
            h = res
            if elapsed_time > seconds or end is True: #elapsed_time > seconds or
                break
            #print(resultat)
        return resultat    # int(math.log10(q)))
    
    
    
    data = sys.stdin.read().splitlines()   # Use Ctrl d to stop the input 
    for i in data:
        m = i.split()
        if len(m) > 1:
            print(ms(int(i.split()[0])) )
        else : pass
        
        
    
  • + 0 comments

    this is far more a problem of math than it is of alg dude must have a masters degree in math to solve this

  • + 0 comments
    #include <iostream>
    using namespace std;
    
    int f (int num) {
        int fact = num;
        if (num == 0) {
            fact = 1;
        }
        else {
        for (int i = num-1; i>0; --i) {
            fact = fact * i;
        }
        }
        return fact;
    }
    
    int fn (int n) {
        int sum_f=0;
        string temp = to_string(n);
        for (int i = 0; i<temp.length(); ++i) {
            int conv_i = temp[i] - 48;
            sum_f += f(conv_i);
        }
        return sum_f;
    }
    
    int sfn (int num) {
        int sum_fn=0;
        int sum_f = fn(num);
        string temp = to_string(sum_f);
        for (int i = 0; i<temp.length(); ++i) {
            int conv_i = temp[i] - 48;
            sum_fn += conv_i;
        }
        return sum_fn;
    }
    
    int gi (int num) {
        int sum_fn;
        int i = 0;
        while (num != sum_fn) {
            ++i;
            sum_fn = sfn(i);
        }
        return i;
    }
    
    int sgi (int num) {
        int sum_gi=0;
        for (int i = 1; i<=num; ++i) {
            int temp = gi(i);
            if (temp < 10) {
                sum_gi += temp;
            }
            else {
                string s_temp = to_string(temp);
                for (int j = 0; j<s_temp.length(); ++j) {
                    int conv_i = s_temp[j] - 48;
                    sum_gi += conv_i;
                }
            }
        }
        return sum_gi;
    }
    
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
        int q, n, m;
        cin >> q;
        for (int i = 0; i<q; ++i) {
            cin >> n >> m;
            cout << sgi(n) << endl;
        }
    }
    
  • + 0 comments

    Any ideas to optimize this code?

    import time
    import math
    import sys
    def sums(n):
       r = 0
       while n:
           r, n = r + n % 10, n // 10
       return r
    def f(n):
        r=0
        s1=0
        while n:
            r, n =  n % 10, n // 10
            s1=s1+math.factorial(int(r))
        return s1
    
    def sf(n):
        return sums(f(n))
    
    def g(i):
        p=1
        while True:
            if sf(p)==i:
                return p
            p=p+1
    
    def sg(i):
        return sums(g(i))
    
    def ssg(n):
        s=0
        for i in range(1,n+1):
            s=s+sg(i)
        return s
    
    q=int(sys.stdin.readline())
    out=[]
    for i in range(q):
        n1,m1=(sys.stdin.readline()).split()
        n=int(n1)
        m=int(m1)
        v=ssg(n)
        out.append(v%m)
    for i in out:
        sys.stdout.write(i)