Leetcode: POW(X,N)

Difficulty: Medium

Implement pow(x, n).

Subscribe to see which companies asked this question

Hide Tags

 Math Binary Search

Show Similar Problems

--------------------------------

--------------------------------

Brutally resolved it in the first mind!

pow(x,10)=x*x*x*x*x*x*x*x*x*x; 

Such way, we did a lot of repeated works, like x*x, which has been calculated, we don't need to do it again!!

So, x^n=(x^ n/2 )^2 * (x^ n%2 ),

 it's a better better way to remove the repeat works in a backtracking way. 

///////////////////////////////////////

//codes

class Solution {

 public:

        double myPow(double x, int n) {

               //check input

               if (n == 0)return 1;

        else if(abs(x)==1){
            if (n%2==0 || x==1)return 1;
            else return -1;
        }

               int b = abs(n);

               double fn = n>0 ? subPow(x, b) : 1 / subPow(x, b);

               return fn;

        }

        double subPow(double base, int n){

               double out;

               if (n == 0)return 1;

               else if (n == 1) return base;

               else{

                      double tmp = subPow(base, n / 2);

                      out = tmp*tmp*(n % 2 ? base : 1);

               }

               return out;

        }

 };

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0)return 1;
        else if(abs(x)==1){
            if (n%2==0 || x==1)return 1;
            else return -1;
        }
        else {
            double out=n>0? bt(x, n) : 1/bt(x, abs(n));
            return out;
        }
    }
    
    double bt(double x, int n){
if (n == 0)return 1;
        else if(n==1)return x;
        else {
            int in = n%2>0 ? (n-1)/2 : n/2;
            
            double res=bt(x, in);
            double out= res*res*(n%2>0 ? x:1);
            return out;
        }
        
    }
};