\[x^y\]

Implement a function to calculate exponentiation x^y quickly. x and y are assumed to be integers.

The key steps in writing an exponentiation function are:

• Return 1 if exponent(power) is 0 because \[x^0 = 1\]
• Return x if exponent(power) is 1 because \[x^1 = x\]
• Check if exponent is <0. If it is, then call the function again with 1/x and -y because \[x^{-y} = 1/x^y\]
• Call function again using x*x and y/2 if exponent is even. Say y = 4, we can write \[x^4 = [x^2]^2\] which is essentially calling function again using x*x and y/2.
• If exponent is odd, say y = 2n+1, we can write \[x^y = x^{2n+1} = x * x^{2n}\]Now 2n is even and we can use the even case again by just multiplying x to it.

int power(int x, int y)
{
    if( x == 0)
        return x;

    //Checking if exponent == 0
    if(y==0)
        return 1;

    //Checking if exponent == 1
    else if(y==1)
        return x;

    //Checking if exponent < 0
    else if(y<0)
        return power(1/x, -1*y);

    //Checking if exponent is even and calling function again using x*x and y/2
    else if(y%2==0)
        return power(x*x, y/2);

    //Checking if exponent is odd and calling function again by making exponent even by taking out one x and multiplying it separately and then using the even case again. 
    else
        return x*power(x*x, y/2);
}

This method runs in O(log y) time.