ps06756 ps06756 - 3 months ago 9
C Question

How to check whether a no is factorial or not?

I have a problem, then given some input number n, we have to check whether the no is factorial of some other no or not.

INPUT 24, OUTPUT true

INPUT 25, OUTPUT false

I have written the following program for it:-

int factorial(int num1)
{
if(num1 > 1)
{
return num1* factorial(num1-1) ;
}
else
{
return 1 ;
}
}

int is_factorial(int num2)
{
int fact = 0 ;
int i = 0 ;
while(fact < num2)
{
fact = factorial(i) ;
i++ ;
}
if(fact == num2)
{
return 0 ;
}
else
{
return -1;
}
}


Both these functions, seem to work correctly.

When we supply them for large inputs repeatedly, then the
is_factorial
will be repeatedly calling
factorial
which will be really a waste of time.

I have also tried maintaining a table for factorials

So, my question, is there some more efficient way to check whether a number is factorial or not?

Answer

It is wasteful calculating factorials continuously like that since you're duplicating the work done in x! when you do (x+1)!, (x+2)! and so on.


One approach is to maintain a list of factorials within a given range (such as all 64-bit unsigned factorials) and just compare it with that. Given how fast factorials increase in value, that list won't be very big. In fact, here's a C meta-program that actually generates the function for you:

#include <stdio.h>

int main (void) {
    unsigned long long last = 1ULL, current = 2ULL, mult = 2ULL;
    size_t szOut;

    puts ("int isFactorial (unsigned long long num) {");
    puts ("    static const unsigned long long arr[] = {");
    szOut = printf ("        %lluULL,", last);
    while (current / mult == last) {
        if (szOut > 50)
            szOut = printf ("\n       ") - 1;
        szOut += printf (" %lluULL,", current);
        last = current;
        current *= ++mult;
    }
    puts ("\n    };");
    puts ("    static const size_t len = sizeof (arr) / sizeof (*arr);");
    puts ("    for (size_t idx = 0; idx < len; idx++)");
    puts ("        if (arr[idx] == num)");
    puts ("            return 1;");
    puts ("    return 0;");
    puts ("}");

    return 0;
}

When you run that, you get the function:

int isFactorial (unsigned long long num) {
    static const unsigned long long arr[] = {
        1ULL, 2ULL, 6ULL, 24ULL, 120ULL, 720ULL, 5040ULL,
        40320ULL, 362880ULL, 3628800ULL, 39916800ULL,
        479001600ULL, 6227020800ULL, 87178291200ULL,
        1307674368000ULL, 20922789888000ULL, 355687428096000ULL,
        6402373705728000ULL, 121645100408832000ULL,
        2432902008176640000ULL,
    };
    static const size_t len = sizeof (arr) / sizeof (*arr);
    for (size_t idx = 0; idx < len; idx++)
        if (arr[idx] == num)
            return 1;
    return 0;
}

which is quite short and efficient, even for the 64-bit factorials.


If you're after a purely programmatic method (with no lookup tables), you can use the property that a factorial number is:

1 x 2 x 3 x 4 x ... x (n-1) x n

for some value of n.

Hence you can simply start dividing your test number by 2, then 3 then 4 and so on. One of two things will happen.

First, you may get a non-integral result in which case it wasn't a factorial.

Second, you may end up with 1 from the division, in which case it was a factorial.

Assuming your divisions are integral, the following code would be a good starting point:

int isFactorial (unsigned long long num) {
    unsigned long long currDiv = 2ULL;
    while (num != 1ULL) {
        if ((num % currDiv) != 0)
            return 0;
        num /= currDiv;
        currDiv++;
    }
    return 1;
}

However, for efficiency, the best option is probably the first one. Move the cost of calculation to the build phase rather than at runtime. This is a standard trick in cases where the cost of calculation is significant compared to a table lookup.

You could even make it even mode efficient by using a binary search of the lookup table but that's possibly not necessary given there are only twenty elements in it.