Factorial as a sum of consecutive number

Question

I was recently solving a problem "No. of ways to express factorial of a number as sum of consecutive number" My solution is :

int fact_as_sum(int n) {  // n is the number whose factorial need to be taken
    long int fact=1;
    int temp=0,count=0;

    for(int i=n;i>0;i--){
        fact*=i;
    }

    printf("%d\n",fact);
    for(int i=fact/2;i>0;i--) {
        int j=i;
        temp=fact;
        while(temp>=0) {
            if(temp==0) {
                count++;
                break;
            }
            else
                temp-=j;
            j--;
        }
    }

    return count;    
}

The solution works correct till small no. of 10!.

But my solution has high complexity. Can anyone suggest a less complex solution ?

Thanks

Answer 1

Ok, so this problem tickled my brain a lot, so first of all thank you for that, I love to solve these kind of problems! I started with a math analysis of the problem in order to find the best implementation, and I came up with this solution:

By defining n as the factorial result number, m the number of sums to be performed and x the starting number for the addition, it all breaks down to the following formula:

.

This can now be simplified, resulting in the following formula:

.

That can be also simplified, giving the following result:

.

Solving for x (the starting number for addition), results in:

.

It is now possible to iterate for all the values of m to find the wanted x value. the lower bound for m is for sure 0, it is not possible to add a negative quantity of numbers! The top bound can be found by noticing that x should be a positive number, it would have no sense to consider negative values that will be nulled by the corresponding positive part! This gives the following result:

That yields the following result:

The negative value of m is discarded as previously said.

This translates in the following C code:

#include <stdio.h>
#include <math.h>

void main() {
    int fact = 8;  //select the wanted factorial to compute
    float n = 1;
    int i;
    float x;
    float m;

    printf("calculating %d factorial...\n", fact);

    for (i = 2; i < fact + 1; i++) {
        n *= (float)i;
    }

    printf("the factorial result is %d\n", (int)n);
    printf("calculating the sum of consecutive numbers...\n");

    //compute the maximum number of iterations
    int maxIter = (int)((-1 + sqrt(1 + 8 * n)) / 2);

    for (i = 0; i < maxIter; i++) {
        m = (float)i;
        //apply the formula
        x = (n / (m + 1)) - (m / 2);
        if (x - (float)((int)x) == 0) {
            printf("found a correct sum!\n");
            printf("the starting number is: %d\n", (int)x);
            printf("the number of sums is: %d\n", i + 1);
        }
    }
}

I've tried this solution on a couple of values and wrote the code for the test, the results seem right. There is an issue with the factorial though, since the factorial reaches very high values quickly, memory needs to be managed better.

Hope I gave an interesting solution, I had fun solving it!

Please correct in case there are problems with this solution.