0
\$\begingroup\$

The objective of this program is to find all factorions, which are numbers equal to the sum of the factorials of their digits.

I am seeking suggestions on how to improve the performance of this code, as well as stylistic advice.

#include <stdio.h>
#include <stdlib.h>
#define base 10 //We are working in base 10
#define upper_bound 2540160 //This is 7 x 9! because a factorion can have at most seven digits.
//If it has d digits, it must satisfy the inequality 10^{d-1} < n <= 9!d, which isn't satisfied above d = 8
#define expected_no_of_answers 5 //I chose 5 somewhat arbitrarily. I knew beforehand there are only four answers in base 10

//Function prototype
void create_hash_table(int[]);
void get_fact_digit_sum(int[],int[]);
void display_answers(int[]);

int main()
{
    int hash_table_fact[base], answers[expected_no_of_answers]; //Creating a hash table where t[n] -> n!

    create_hash_table(hash_table_fact);

    get_fact_digit_sum(answers,hash_table_fact);

    display_answers(answers);

    return 0;
}

void create_hash_table(int hash_table_fact[])
{       
    int i = 1, fact = 1;
    hash_table_fact[0] = 1; //0! = 1

    for(i = 1; i < base; i++)
    {
        fact = fact*i;
        hash_table_fact[i] = fact;
    }
}

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
    int answerCount = 0, i = 1, temp, sum;

    //Combing through the search space to search for factorions
    for(i = 1; i <= upper_bound; i++)
    {
        temp = i;
        sum = 0;
        //Getting the sum of the factorials of the digits
        while(temp != 0)
        {
            sum = sum + hash_table_fact[ (temp%base) ];
            temp = temp/base;
        }
        if(sum == i)
        {
            answers[answerCount++] = i;
        }
    }

    //Placing a 0 at the end to mark the end of the array
    answers[answerCount] = 0;
}

void display_answers(int answers[])
{
    int i;

    for(i = 0; answers[i] != 0; i++)
    {
        printf("%d\t",answers[i]);
    }
}
\$\endgroup\$
  • \$\begingroup\$ OK, so what do you expect to get out of this code review? \$\endgroup\$ – user633183 Feb 13 '17 at 23:45
  • \$\begingroup\$ How to improve it in terms of performance and writing style. \$\endgroup\$ – user230452 Feb 14 '17 at 0:11
  • \$\begingroup\$ @naomik I didn't state it explicitly because I thought it is understood in all questions on this site. \$\endgroup\$ – user230452 Feb 14 '17 at 0:12
  • \$\begingroup\$ meta.codereview.stackexchange.com/questions/2436/… \$\endgroup\$ – user633183 Feb 14 '17 at 0:13
3
\$\begingroup\$

You can use the previous sum to compute the next one

Your main loop computes the sum of factorials of digits from scratch for each number, but you are throwing away a lot of work from number to number. Think about two consecutive numbers, such as:

1234: sum = 1! + 2! + 3! + 4!
1235: sum = 1! + 2! + 3! + 5!

You can see that for 1235, it only differs from 1234 by the last digit, so you can compute its sum more quickly if you do this:

sum = previousSum + 5! - 4!

If the last digit wraps around from 9 to 0, you have to do the same thing with the next digit on the left:

1239: sum = 1! + 2! + 3! + 9!
1240: sum = 1! + 2! + 4! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 4! - 3! // Tens digit

If you reach a new power of 10, you need to do something a little different:

 99: sum =      9! + 9!
100: sum = 1! + 0! + 0!

sum  = previousSum;
sum += 0! - 9! // Ones digit
sum += 0! - 9! // Tens digit
sum += 1!      // Hundreds digit (note: do not subtract 0!)

Sample rewrite

Using this idea, your function becomes this:

void get_fact_digit_sum(int answers[], int hash_table_fact[])
{
    int answerCount = 0;
    int sum         = 1;

    // Combing through the search space to search for factorions
    for (int i = 1; i <= upper_bound; i++) {
        int temp = i;

        while (1) {
            int digit = temp % base;
            if (digit == 0) {
                sum += hash_table_fact[0] - hash_table_fact[base-1];
                temp /= base;
                if (temp == 1) {
                    // Special case: reached new digit.
                    sum += hash_table_fact[1];
                    break;
                }
            } else {
                sum += hash_table_fact[digit] - hash_table_fact[digit-1];
                break;
            }
        }
        if (sum == i) {
            answers[answerCount++] = i;
        }
    }

    // Placing a 0 at the end to mark the end of the array
    answers[answerCount] = 0;
}

The new way ran 4x faster than the old way for the given upper bound. If you extend the upper bound to 100 million (even though there are no answers that high), the new way runs 8x faster than the old way.

\$\endgroup\$
  • \$\begingroup\$ Fantastic idea ! Have you done this before ? Thanks a lot. \$\endgroup\$ – user230452 Feb 15 '17 at 1:59
  • \$\begingroup\$ Are you a mathematician ? \$\endgroup\$ – user230452 Feb 15 '17 at 1:59
  • \$\begingroup\$ @user230452 I used this technique before for some other problem similar to this one. No I'm not a mathemetician. Here, I found the similar question that used the same technique to solve. \$\endgroup\$ – JS1 Feb 15 '17 at 2:24
  • \$\begingroup\$ Well done. I will implement this technique on another program and upload it soon and it's very similar to the question you linked. You can check it out and give your comments. \$\endgroup\$ – user230452 Feb 15 '17 at 2:54
  • \$\begingroup\$ I encountered this kind of problem (requiring sum of digits) and variations for the first time in eight grade. (About 8 years back.) Every time I get this kind of problem, I just think of the same thing. This thought of optimizing it never occurred to me. Thanks ! \$\endgroup\$ – user230452 Feb 15 '17 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.