Exponentiation By Squaring - Java 1ms AC


  • 2
    O
    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


Log in to reply
 

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