Posts Power Function
Post
Cancel

Power Function

Problem Description

Given integers A and N, find A power N. (Recursive Approach)

leetcode

Solution

A simple way to solve recursively is by doing something like:

1
2
3
4
5
6
public static int calc(int a, int n) {

    if(n == 0) return 1;
    return a * calc(a, n-1);

}

This works but it takes O(n) time. We can optimize it futher using the following approach, which gives us the power in O(logN) time.

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
package recursion;

public class Power {

public static void main(String[] args) {
    System.out.println(pow(3, 3));
}

public static int pow(int a, int n) {
    
    if(n == 0) return 1;
    
    int halfExponent = pow(a, n/2);
    int halfAnswer = halfExponent*halfExponent;
    
    if(n%2 == 0) {
        return halfAnswer;
    }else {
        return halfAnswer*a;
    }
    
}

}

Handling Negative Powers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public double myPow(double a, long n) {

        if(n == 0) return 1;

        long N = n;
        if (N < 0) {
            a = 1 / a;
            N = -N;
        }

        double halfExponent = myPow(a, N/2);
        double halfAnswer = halfExponent*halfExponent;
        
        if(N%2 == 0) {
            return halfAnswer;
        }else {
            return halfAnswer*a;
        }

    }
    
}
This post is licensed under CC BY 4.0 by the author.