Cognzant Technology Solutions Interview Question
Android EngineersCountry: India
Interview Type: Written Test
Swift
///func factorial(n:Int, result:Int = 1)->Int {
/// if n < 1 { return result }
/// return factorial(n - 1, result: result * n)
///}
///func nfactorial(n:Int, result:Int = 0)->Int {
/// if n < 1 { return result }
/// return nfactorial(n - 1, result: factorial(n) + result)
///}
nfactorial(5) // 153
// I did read the problem wrong. Need new glasses. Thanks!
func factorial(n:Int, result:Int = 1)->Int {
if n < 1 { return result }
return factorial(n - 1, result: result * n)
}
func nfactorial(n:Int, val:Int = 1, result:Int = 0)->Int {
if val > n { return result }
let f = factorial(val)
let m = val % 2 == 0 ? (result - f) : (result + f)
return nfactorial(n, val:val + 1, result:m)
}
Observation:
As there are only 3 elements of series it's hard to assume anything. But if the assumption of deducting even factorial from the previous odd factorial.
here is the solution with O(1) space and O(n) time
def fancyFactorial(n):
n1fact = 1
result = 1
if n <= 1:
return n1fact
i = 2
while i <= n:
n1fact = n1fact * i
if i % 2 == 0:
result = result - n1fact
else:
result = result + n1fact
i += 1
return result
// return 1! - 2! + 3! - 4!... n!
public static int calculate(int n) {
int []factorial = new int[n];
factorial[0] = 1; //1!
int result = factorial[0];
for(int i=2;i<=n;i++) { // i = 1
factorial [i-1] = factorial[i - 2] * i;
if(n % 2 == 0) {
result -= factorial[i-1];
} else {
result += factorial[i-1];
}
}
return result;
}
Time Complexity : O(n) for iterations, O(1) - constant access for array
Space Complexity : Additional space of size n
- Roman August 16, 2016