Calculate Pow(x, n)

Say we are given two integers, x, n, and we need to find the xⁿ without using any inbuilt methods in any programming language. In this article we will discuss the iterative and recursive approaches and their complexities to solve the given problem.

It is recommended to use each approach on the basis of their application. Using such methods during calculation makes the program efficient and using inbuilt functions will help us with code reusability. But to use any inbuilt method we should be aware of its time and space complexity.

Examples:
Input : x=4, n=2
Output : 16

Input : x=8, n=2
Output : 64

Iterative Approach

We can iterate from i=1 to n and multiply x to n number of times to itself to get the result.

Algorithm

Declaration

x, n --> Integer
result =1 —> long integer (to store long result)
Step1: Take x and n input
Step2: Calculate pow(x, n) method
Step3: Loop i= 1 to n ( n times)
result =result * x;
Step4: Return result

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
import java.lang.*;

class Solution {
  static long pow(int x, int power) {
    if (power == 0)
      return 1;
    long result = 1 L;

    for (int k = 1; k <= power; k++) {
      result = result * x;
    }

    return result;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter x:");
    int x = sc.nextInt();

    System.out.println("Enter n:");
    int n = sc.nextInt();

    System.out.println("\n\nPow(" + x + "," + n + "):" + pow(x, n));

  }

}

Output Snippet

Complexity Analysis

Time Complexity: O(N) because we are iterating once till N.

Space Complexity: O(1) No extra space has been used.

Recursive Approach

We will call the pow(x,n) method for calculating and the same method will call itself passing x and n-1. We will give a base condition to come out of the recursive function call.

Algorithm

Declaration

x, n --> Integer
Step1: Take x and n input
Step2: Calculate pow(x, n) method
check base condition if n==0 return 1
check base condition if n==1 return x
recursively call pow(x,n-1) and go to step 2;
Step 3: Print result

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
import java.lang.*;

class Solution {

  static long pow(int x, int power) {
    //System.out.println(x+":"+power);
    //base condition 
    if (power == 0)
      return 1 l;

    if (power == 1)
      return x;
    power--;
    return x * pow(x, power);

  }
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter x:");
    int x = sc.nextInt();

    System.out.println("Enter n:");
    int n = sc.nextInt();

    System.out.println("\n\nPow(" + x + "," + n + "):" + pow(x, n));

  }

}

Output Snippet

Complexity Analysis

Time Complexity: O(N) because pow(x,n) is called recursively for each number from 1 to n.

Space Complexity: O(1) No extra space has been used.

Divide and Conquer (Efficient)

We will use the divide and conquer technique to improve the time complexity by calling pow(x, power/2).

Algorithm

Declaration

x, n --> Integer
Step1: Take x and n input
Step2: Calculate pow(x, n) method
check for base condition if n==1 return 1
check if n is even
call pow(x, n/2) * pow(x, n/2) //step 2
if n is odd
call pow(x, n/2) * pow(x, n/2) //step 2
Step 3: Print result

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
import java.lang.*;

class Solution {

  static long pow(int x, int power) {
    //System.out.println(x + ":" + power);
    //base condition 
    if (power == 0)
      return 1 L;

    if (power == 1)
      return x;
    log res = pow(x, power / 2);
    //if power is even
    else if (power % 2 == 0)
      return res * res;

    else
      return x * res * res; //if power is odd
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter x:");
    int x = sc.nextInt();

    System.out.println("Enter n:");
    int n = sc.nextInt();

    System.out.println("\n\nPow(" + x + "," + n + "):" + pow(x, n));

  }
}

Output Snippet

Complexity Analysis

Time Complexity: O(log N) because pow(x,n/2) is calculated and then stored for again using the same result.

Space Complexity: O(1) No extra space has been used.

Ref for more elaboration:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring