# Iterative Power (Binary Exponentiation)

Sun Feb 06 2022 05:47:23 GMT+0000 (UTC)

```// Efficient Method : Time Complexity : θ(logn), Auxiliary Space: θ(1)

import java.io.*;
import java.util.*;

public class Main {

static int power(int x, int n)
{
int res = 1;

while(n>0)
{
if(n%2 != 0)
{
res = res * x;
x = x*x;
n = n/2;
}
else
{
x = x*x;
n = n/2;
}
}

return res;
}

public static void main (String[] args) {

int x = 3, n = 4;

System.out.println(power(x, n));

}
}```
content_copyCOPY

3^10 = 3^8 * 3^2 3^19 = 3^16 * 3^2 * 3^1 10 : 1010 (3^8 * 3^4 * 3^2 * 3^1) 1.) Every numbers can be written as sum of powers of 2 (set bits in binary representation) 2.) We can traverse through all bits of a number (From LSB to MSB in O(logN) time. while (n is greater than 0) { if(n%2 != 0) // Bit is 1 else // Bit is 0 n = n/2; } --------------------------------------------- x=4, n =5 Initially : res = 1 1st Iteration : res = 4 x = 16 n = 2 2nd Iteration : res = 4 x = 16 * 16 = 256 n = 1 3rd Iteration : res = 4 * 256 = 1024 x = 256 * 256 = 65,536 n = 0 --------------------------------------------- 5 : 1001 (4^8 * 4^4 * 4^2 * 4^1) res = 4^4 * 4^1