# 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)
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://www.firecode.io/blog/4-problem-of-the-week---power?id=805-problem-of-the-week---loop-in-a-singly-linked-list", "fetch_time": 1569314114000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-39/segments/1568514572896.15/warc/CC-MAIN-20190924083200-20190924105200-00275.warc.gz", "warc_record_offset": 888817637, "warc_record_length": 7059, "token_count": 470, "char_count": 1723, "score": 3.953125, "int_score": 4, "crawl": "CC-MAIN-2019-39", "snapshot_type": "longest", "language": "en", "language_score": 0.8438029885292053, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00062-of-00064.parquet"}