## Problem

Implement pow(*x*, *n*).

## Analysis

Divide and conquer, first compute pow(x, n/2), then use it to compute pow(x,n). Need to consider

– n is odd or even

– if n is odd, need to consider n is positive or negative

## Solution

class Solution { public: double myPow(double x, int n) { if(x==0) return 0; if(n==0) return 1; //divide and conquer int half = n/2; double val = myPow(x, half); //check if n is odd or even if(n%2 == 0) return val*val; else{ //check if n is positive or negative if(n>0) return val*val*x; else return val*val/x; } } };