# Sharing my 1ms Java solution with pseudocode

• /*
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);
}
``````

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

• 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.

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

• @rowena000
You are more than welcome.

Thanks

• Very specific explanation! Thanks!

• Hello @lxd

Thanks a lot, I appreciate it

• thanks a lot!!

• You are more than welcome.

Thanks

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