Calculate power

Problem

Calculate x to the power y.

Constraint

Complexity should be less than O(n).

Solution

Suppose we are trying to calculate x to the power y and y is 4. Then we can do result=1; Then 4 times (result=result*x). In this way the complexity is O(n). In another way, we can do result=x*x; then we can do result =result *result; in this way the number of multiplication is 2 but y=4. So for power of 2s we can clearly see the number of multiplication is log(n) time. What happens for other numbers like when y=7. We can divide seven in 4+2+1. so x^(4+2+1)=(x^4) * (x^2) * (x^1).

So we can see that all powers are now divided into power of some numbers which are powers of 2. For example x^y where y is 13, we can do 8+4+1. Clearly we can see when y is represented in binary, the set bits are indicative of how to calculate the result. So whenever the bit is set multiply the powers to the result. and then do power=power*power for the next bit.

Code

public class CalculatePower
{
 public static void main(String[] args)
 {
  int x = 4;
  int y = 10;
  long power = x;
  long answer = 1;
  while (y != 0)
  {
   if ((y & 1) == 1)
   {
    answer *= power;
   }
   y >>= 1;
   power *= power;
  }
  System.out.println(answer);
 }
}