O(1) Java Solution


  • 0
    S

    The way to do this in constant time is to use the properties of logarithms and handle a few special cases such as negative numbers.

    public class Solution {
        public double myPow(double x, int n) {
            if (n==0) return 1;
            double nd=n;
            double total=1;
            boolean neg=false;
            boolean negNum=false;
            if (n<0) { neg=true; nd = -nd; }
            if (x<0) { x=Math.abs(x); if (n%2==1) { negNum=true; }}
            total=Math.exp(Math.log(x)*nd);
            //System.out.println("total "+total);
            if (neg){ 
                total=1.0/total;            
            }
            if (negNum) {
                total=-total;
            }
            return total;
        }
    }
    

  • 0
    S

    @squinky FYI, Math.pow() is implemented in constant time in the Java standard library using logarithms and exponents: https://stackoverflow.com/questions/32418731/java-math-powa-b-time-complexity


Log in to reply
 

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