Leetcode

Pow(x, n)

  • Time:O(\log n)
  • Space:O(1)

C++

class Solution {
 public:
  double myPow(double x, long n) {
    if (n == 0)
      return 1;
    if (n < 0)
      return 1 / myPow(x, -n);
    if (n & 1)
      return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
  }
};

JAVA

class Solution {
  public double myPow(double x, long n) {
    if (n == 0)
      return 1;
    if (n < 0)
      return 1 / myPow(x, -n);
    if (n % 2 == 1)
      return x * myPow(x, n - 1);
    return myPow(x * x, n / 2);
  }
}

Python

class Solution:
  def myPow(self, x: float, n: int) -> float:
    if n == 0:
      return 1
    if n < 0:
      return 1 / self.myPow(x, -n)
    if n % 2:
      return x * self.myPow(x, n - 1)
    return self.myPow(x * x, n / 2)