Compute 2 to the power of n recursively and print it. What is the most efficient way to split the problem into smaller subproblems?
Example
Input:
var n = 5Expected value/output:
32
[collapse]
Hint
2^n = 1, n = 0
2^n = 2^(n-1) * 2, n > 0
or
2^n = 1, n = 0
2^n = 2^(n/2) * 2^(n/2), n > 0 & n is even
2^n = 2^(n/2) * 2^(n/2) * 2, n > 0 & n is odd
[collapse]
Solution
var n = 5
func pow2N(N:Int) -> Int {
if N == 0 {
return 1
}
else {
var halfN = N/2
var halfPowN = pow2N(N: halfN)
var res = halfPowN * halfPowN
if N - halfN > halfN {
res *= 2
}
return res
}
}
var pow2n = pow2N(N:n)
print(pow2n)[collapse]
