# Problem of the week - Power

Ashish Srivastava | @ashishsrtechie | 5 Oct, 2015

Google has positioned itself as a dream company for almost all software engineers for quite some time now. With one of the lowest interview success rates and some of the hardest coding interview questions, getting a job at Google as a software engineer is hard, BUT, it's not a moonshot. This week, we will practice a problem that is an interview favorite with many current and ex Googlers - Power.

Function to calculate x^n - power(x,n)
x: base value
n: power value

### Approach 1 :

#### Hint: Divide and Conquer

Divide the problem into sub-problems with an exponent n/2 and recursively get to the final answer.

#### Implementation:

```int power(int x, int n)
{
if( n == 0)
return 1;
else if (n%2 == 0)
return power(x, n/2)*power(x, n/2);
else
return x*power(x, n/2)*power(x, n/2);
}
```

Neat, isnâ€™t it? let's check the space and time complexities.
Time Complexity: O(n)
Space Complexity: O(1)

That's a smart answer, and you should give yourself a high-five if you got this far. But this being a Google interview - you're asked to optimize the solution and bring down the time complexity to O(log n).

### Approach 2 :

#### Implementation:

```int power(int x,  int n)
{
if( n == 0)
return 1;
tempAnswer = power(x, n/2); // Calculate once and store.
if (n%2 == 0)
else
}
```

Ok, that's much better. But did we consider negative inputs? This answer cannot be complete without that - and you'll probably be put on the spot if you skipped on those. Always consider the edge cases - null, 0, negative - they're all fair game!

#### Implementation:

```float power(float x, int n)
{
if( n == 0)
return 1;
if (n%2 == 0)
else
{
if(n > 0)