ps06756 - 6 months ago 18

C 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`

`factorial`

I have also tried maintaining a table for factorials

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.