geeksforgeeks/fact_digit_sum.c at master · svshyam91/geeksforgeeks · GitHub

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
    Fact Digit Sum
    Problem Link: https://practice.geeksforgeeks.org/problems/fact-digit-sum/0

    Author: Shyam Kumar
    Date: 12-09-2019

*/


#include <stdio.h>

int fact( int num, unsigned long int *fact_arr ) {
    /* This function returns the factorial of num */

    if( fact_arr[num] != 0 )
        return fact_arr[num];
    else
        return num*fact(num-1, fact_arr);

}

int fact_digit_sum( int x, int i ) {

    // printf("i = %d\n",i);
    unsigned long int fact_arr[10] = {0}, f;
    fact_arr[0] = fact_arr[1] = 1;

    unsigned long long int sum = 0;
    int num = i, rem;

    /* Finding the sum of factorial of digits */
    while(num != 0) {
        rem = num%10;
        f = fact(rem, fact_arr);
        fact_arr[rem] = f;
        sum += f;
        // printf("fact of %d=%u\n",rem,f);
        num = num/10;
    }

    /* If the found sum is equal to given number */
    if( sum == x )
        return i;
    return fact_digit_sum(x, i+1);

}

int main() {

    int t, ans;
    unsigned long long int x;

    scanf("%d",&t);
    while(t>0) {
        scanf("%llu",&x);
        ans = fact_digit_sum(x, 1);
        printf("%d\n",ans);
        t--;
    }
	return 0;
}