How to check whether a no is factorial or not?

Question

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?

Solution 1

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.

Solution 2

If the number is a factorial, then its factors are 1..n for some n.

Assuming n is an integer variable, we can do the following :

int findFactNum(int test){
  for(int i=1, int sum=1; sum <= test; i++){
    sum *= i; //Increment factorial number
    if(sum == test)
        return i; //Factorial of i

   }
return 0; // factorial not found
}

now pass the number 24 to this function block and it should work. This function returns the number whose factorial you just passed.

Solution 3

You can speed up at least half of the cases by making a simple check if the number is odd or even (use %2). No odd number (barring 1) can be the factorial of any other number

Comments

[VirtualThread]

Also if you are not very interested in high range (you are using int), then you only need an array of 13 values. Beyond that no other factorial will fit in the int range. You can thus have best case O(1) time and work case O(nlog(n)) time.

[songyuanyao]

printf("it is a factorial",a); ?

[lokesh5790]

Thanks!! have rectified it

[Pang]

The question is tagged C. This answer is not in C. This answer is wrong.