// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(logn)
import java.io.*;
import java.util.*;
public class Main {
static int power(int x, int n)
{
if(n == 0)
return 1;
int temp = power(x, n/2);
temp = temp * temp;
if(n % 2 == 0)
return temp;
else
return temp * x;
}
public static void main (String[] args) {
int x = 3, n = 5;
System.out.println(power(x, n));
}
}
// Naive Method : Time Complexity : θ(n)
static int power(int x, int n)
{
int res = 1;
for(int i=0; i<n; i++)
{
res = res * x;
}
return res;
}
