Sharing my java solution, o(log(n)) time and o(1) space. it is a bit long though.


  • 1
    M
    public class Solution {
        public double pow(double x, int n) {
            
            if (x == 1.0)
                return 1;
            else if (x == -1.0){
                if (n %2 == 0){
                    return 1;
                }else
                    return -1;
            }
                
            int absn = 0;
            if (n < 0){
                absn = -n;
            }else
                absn = n;
            
            
            double returnValue = 1;
            int temp = absn;
            int i = 0;
            int mask = 1;
            while (temp != 0){
                if ((temp & mask) > 0){
                    returnValue *= p(x, i); 
                }
                temp = temp >> 1;
                i++;
            }
            
            if (n < 0)
                return 1.0/returnValue;
            else 
                return returnValue;
        }
        
        
        private double p(double x, int power){
            double val = x;
            
            for (int i=0; i<power; i++){
                val *= val;
            }
    
            return val;
        }
    }

  • 0
    S

    You could add x *=x inside

     while (temp != 0){
                if ((temp & mask) > 0){
                    returnValue *= p(x, i); 
                }
                temp = temp >> 1;
                i++;
            }
    

    this loop instead of using another function.

     while (temp != 0){
                    if ((temp & mask) > 0){
                        returnValue *= x; 
                    }
                    x *= x;
                    temp = temp >> 1;
                    i++;
                }
    

    That will make your method O(1) in run time.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.