Exponentiation By Squaring - Java 1ms AC

• ``````public double myPow(double x, int n) {
if (n == 0) return 1.0;
if (n < 0) { x = 1 / x; n = ~n + 1; }
if (n == 1) return x;
if (n == 2) return x * x;
if ((n & 1) == 1) return x * myPow(x * x, n >> 1);
return myPow(x * x, n >> 1);
}
``````
• Anything raised to the 0th power is 1.
• Anything raised to a negative power is it's reciprocal raised to a positive power of the same magnitude.
• Anything raised to the 1st power remain unchanged.
• Raising anything to the second power just multiplies itself once.
• Anything raised to an arbitrary odd power is itself multiplied by its second power raised to half the original power.
• Anything raised to an arbitrary even power is it's second power raised to half the original power.

The halfing and squaring makes the algorithm logarithmic with respect to n i.e O(log n).
https://en.wikipedia.org/wiki/Exponentiation_by_squaring

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