Compute 2 to the Power of N

Sawing

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 = 5

Expected 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]
Subscribe
We send about one email per week with our latest tutorials and updates
Never display this again :)