Interview Questions And Answers 
-
Write a function to compute the factorial of a given integer.
5,750 Views |
(14 votes, avg: 3.71)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Write a function to compute the factorial of a given integer.
5,750 Views | (14 votes, avg: 3.71)
Loading ...
factorial (n)
{
if n=0 then return 1
else return n*factorial(n-1)
}
Loop is faster than recusive, so, here is a loop version:
int factorial( int n)
{
int i;
int result =1;
for (i=n; i>0; i–)
result *= i;
return result;
}
Either iterative or recursive the alghoritm must be aware for the case of a negative parameter.
The above functions are confused by a negative value: the iterative reports 0 without a warning and worsely the recursive alghoritm will enter an infinite loop
well the above function can be reduced to more cryptic module.
fact(int n)
{return(n>0?(n*fact(n-1)):1)}
to a more cryptic one
fact(n){return fact(n-1)*n+!n;}
yeah but works only for n>=0.
My function is gonna work for both +ve and
-ve integers.
int factorial (int n)
{
int i ;
int result = 1 ;
if ( n = 0)
return result;
if ( n > 0)
{
for (i = n ; i > 0 ; i–)
result = result*i;
}
if ( n < 0)
{
for (i = n ; i < 0 ; i++)
result = result*i;
if (result > 0)
result = result - 2*result;
}
return result ;
}
Mohit.. what the hell does factorial for a negative integer mean ???????
Just use a look up table!! That is the fastest way.
int fact(int n)
{
return(n>0?(n*fact(n)):1);
}
int fact(int n)
{
return(n>0?(n*fact(n-1)):1);
}
a single function
int a=fact(n);
The factorial of a negative integer is not defined. But I think you’ve better say this to the interviewer BEFORE he tries to trick you into thinking it’s defined.
ok… this one is itr. and faster
int fc(int i){
int j, i, factorial=1;
for (j=i, j>1;j–)
factorial *= j;
return factorial;
}
but if recursive is prefered then:
int fc(int i){
if (i > 1)
return n*fc(n-1);
else
return 1;
}
Use Dynamic Programming Please…do not call all these recursive functions again and again..
#include
int factorial(int i){
if (i==0)
return 1;
else
return i * factorial(i-1);
}
int main(){
for (int i =0; i
One thing need to be taken care in the above programs is that datatype can be taken as “unsigned int” instead of “int”, considering the fact that we don’t calculate the factorial for -ve numbers.
It will double the range of the result.
Both recursive and non recursive implementaions are fine.
if you want the accurate result you should use array and stack. the result will be very large when you give an big n for example 10000
I think a lookup table is a legitimate solution, in O(1).
The table will be pretty small, as for a 32 bit integer for instance, you will be able to calculate the n! for at most n = 32, because n! >> 2^n and 2^32 is the maximal integer to be stored with 32 bits. Actually the n! grows much faster - O(n^n), but 2^n bound is enough for our argument.
So a lookup table would only need to have 32 entries. Method would check whether n
Continuing from the first post:
So a lookup table would only need to have 32 entries. Method would check whether n is smaller than 32 and return table[n], otherwise throw error or return 0.
For the 64 bit integer the bound is likewise 64 (although the real one is intuitively much smaller).
So yeah, this is a practical O(1) solution in my book.
Leave an Answer/Comment