Amazon Interview Question
Software Engineer / Developerslong factorial(int n) {
long[] values = new long[n+1];
values[0] = 1;
for (int i = 1; i <= n; i++) {
values[i] = i * values[i - 1];
}
return values[n];
}
class FactorialHolder {
private static final int SIZE_OF_ARRAY = ??; // maximum of n satisfying n! < MAX_LONG
private static long[] values = new long[SIZE_OF_ARRAY];
static {
for(int i=0;i<SIZE_OF_ARRAY;i++) {
values[i] = 0;
}
values[1] = 1;
}
public static long factorial(int n) {
return values[n]>0 ? values[n] : values[n]=factorial(n-1)*n;
}
public static long factorialIterative(int n) {
int i;
for(i=n;i>=1;i--) {
if (values[i]!=0) break;
}
for(i=i+1;i<=n;i++) {
values[i] = values[i-1]*i;
}
return values[n];
}
}
Problem:
-----------
Find Nth factorial
Example:
------------
N=5
Factorial F = 5*4*3*2*1 = 120
Algo/Solution:
-----------
Input : Factorial int N
A for loop which will decrement i from N to 0
and keep on multiplying with its value
Output : result
Code:
--------------
Private int NFactorial(Int N)
{
For (int i=N , i > 0,i-- )
{
int result *=i;
}
return Result;
}
HandRun:
--------------
N=5
i=5
5
5*4=20
20*3=60
60*2=120
120*1=120
Order:
-----------
O(N)
long factorial(int n){
- biggied88 March 02, 2010value = 1;
while(n > 0){
value = value * n;
n = n - 1;
}
return result;
}