# LeetCode Medium 50. Pow(x, n)

tags: leetcode

問題

• Explore
• Problems

$x^{n}$を計算するpow(x, n)を実装せよ

注意: $$ -100.0 < x < 100.0 $$ $$ n \in [- 2^{31}, 2^{31}) $$

解法1(recursive)

愚直に実装するとxをn回掛ける必要があるので時間計算量が$O(n)$となり効率が悪いです

改善するために下の工夫をします

• 基底は$n=0$のときです.このとき$1$を返します
• $n$が偶数の時は$x^{n}$を$x^{2 \cdot n/2}$と表せることを使ってpow(x*x, n/2)を再帰的に実行します
• また$n$が奇数のときは$n-1$として偶数にして上の処理をした関数の帰り値にxを掛けます
• $n < 0$のときはx = 1/x, n = -nとして再帰関数を実行します
• 空間計算量は上の処理で$n=2^{x}$である$x$回だけ実行すればよいので, $O(\log(n))$
• 時間計算量も$O(\log(n))$です

Python

再帰回数の上限

Pythonは再帰関数の上限が決まっています.以下のコードでその上限値を見ることが可能です

import sys
print(sys.getrecursionlimit()) # 1000 

この問題では再帰で実装した際に上限に達してしまう可能性があるのでこの上限を変更します

sys.setrecursionlimit(10 ** 9)

今回は上限を変えなくても大丈夫です(LeetCodeに関して言えば, これを使っているときはアルゴリズムがおかしい可能性が高い気がします)

コード

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

C++

C++ではmyPowのみを使って再帰での実装は出来ないはずです

lambdaやhelper関数を使えばできるかも知れませんがおそらくこの点で聞きたいのは2の補数を理解しているかなのでいらないと思います

C++のint型は$[- 2^{31}, 2^{{31}})$です

つまり負の数の最大値の絶対値は正の数の最大値の絶対値よりも1大きいです

そのためC++では次の方法で実装すると上手く行かないです

下は上手く行かない例です

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

解法2(iterative)

• 上と同じことをします
• 再帰関数を使わないで返り値となる変数を使います(ここではres)
• 空間計算量と時間計算量はrecursiveのときと変わりません

Python

class Solution:
    def myPow(self, x: float, n: int) -> float:
      if n == 0:
        return 1
      else:
        res = 1
        if n < 0:
          x, n = 1/x, -n
        while n != 0:
          if n & 1:
            res *= x
          x *= x
          n //= 2
        return res

C++

class Solution {
public:
    double myPow(double x, int n) {
      double res = 1.0;
      for (int i = n; i ; i /= 2) {
        if (i & 1)
          res  *= x;
        x *= x;
      }
      if (n >= 0) {
        return res;
      } else {
        return 1 / res;
      }
    }
};

ちなみに

Pythonならこう書けば終わりです...(身も蓋もない)

return x**n