Sharing my 1ms Java solution with pseudocode


  • 5
    A

    /*
    PSEUDOCODE:

    If n is 0, we return 1 since any number to the power of 0 is 1
    if n is 1, we return x since any number to the power of 1 is itself
    if n < 0, we return (1/x) * myPow(1/x, -(n+1))
    We could have just return myPow(1/x, -n), but we want to avoid overflow for the case where n is at the borderline
    of negative integers (i.e, n = -2147483648).
    Example, x^(-3) = (1/x)^3 = (1/x) * (1/x)^2 = (1/x) * (1/x)^(-(-2)) = (1/x) * [(1/x)^(-(-3+1)] = 1/x * [(1/x)^2]

    For all other cases, we do the followings:

    We know that, for any integers n and k, we can rewrite n as: n = k * (n/k) + (n % k).
    For k = 2, n = 2 * (n/2) + (n % 2).

    Example:
    7 = 2*(7 / 2) + 7 % 2 = 2*(3) + 1
    6 = 2*(6 / 2) + 6 % 2 = 2*(3) + 0
    4 = 3*(4 / 3) + 4 % 3 = 3*(1) + 1

    We will be using the formulas below to simplify:

    pow(x, ab) = pow(x, ba)
    pow(x, a+b) = pow(x, b+a)
    pow(x, ab) = pow(pow(x, a), b), i.e. x^(ab) = (x^(a))^b
    pow(x, a+b) = pow(x, a) * pow(x, b), i.e x^(a+b) = (x^a) * (x^b)

    Since n = 2 * (n/2) + (n % 2), we have:
    pow(x, n) = pow(x, [ 2*(n/2) + (n%2) ] ) = pow(x, 2*(n/2) ) * pow(x, (n%2)) =
    = pow(x, (n/2)*2 ) * pow(x, (n%2)) = pow( pow(x, n/2), 2) * pow(x, (n%2))

    Using the ^ sign, we can rewrite the above formula as:
    x^n = x^[ 2*(n/2) + (n % 2) ] = x^( 2*(n/2) ) * x^(n % 2) =
    = [ x^( (n/2)*2 ) ] * x^(n % 2) = [ (x^(n/2)) ^ 2 ] * x^(n % 2)

    Let y = pow(x, n/2), i.e y = x^(n/2)
    Also, let r = n % 2 and z = pow(x, n%2) = pow(x, r).

    Therefore,
    result = pow(x, n) = pow( pow(x, n/2), 2) * pow(x, (n%2)) =
    = pow(y, 2) * pow(x, r) = (y^2) * (x^r) = (y*y) * (x^r)

    But, since r = n%2 is either 0 or 1, x^r is therefore either 1 (if r=0) or x (if r=1)
    Thus, our result will be:
    if r = n%2 = 0, result = (yy). Otherwise, result = (yy) * x
    ( Remember y = pow(x, n/2) = x^(n/2) )
    */

    public double myPow(double x, int n) {
            if (n == 0) return 1;
            if (n == 1) return x;
            if (n < 0) return ( (1/x) * myPow(1/x, -(n+1)) );
            
            double y = myPow(x, n/2);
            double z = y*y;
            int r = n % 2;
            
            return (r == 0) ? z : (z * x);
        }
    

  • 0
    R

    Could you please explain why it overflows when n is -2147483648?


  • 0
    A

    Hello @rowena000

    For sure. Remember an integer is between the values of -2147483648 and 2147483647
    If n = -2147483648, then -n = 2147483648; therefore -n is greater than the largest possible integer value, thus -n is not an integer. And remember, myPow's 2nd input n must be an integer. Because the value being passed here (-n) is not an int, the compiler will complain :(

    However, if n = -2147483648, then -(n+1) = -( -2147483648 + 1) = 2147483647, which is an integer; we can then pass this value to myPow without the compiler complaining.

    I hope this was helpful


  • 0
    R

    Thank you very much!
    I've never noticed the two numbers have a difference of 1! I'll keep that in mind.


  • 0
    A

    @rowena000
    You are more than welcome.

    Thanks


  • 0
    L

    Very specific explanation! Thanks!


  • 0
    A

    Hello @lxd

    Thanks a lot, I appreciate it


  • 0
    M

    thanks a lot!!


  • 0
    A

    Hi @Mercy226

    You are more than welcome.

    Thanks


Log in to reply
 

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