   Type like pro

# 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;