45. Pow(x, n)

読了目安 約1分

Recursion / LeetCode 50 (Medium) — x の n 乗を繰り返し二乗法で O(log n) で計算する。

問題

LeetCode 50. Pow(x, n)（Medium / カテゴリ: Recursion）

実数 x と整数 n が与えられ、x の n 乗を計算します。 n は負にもなります。 x を n 回掛ける O(n) では遅く、O(log n) が求められます。

考え方

Swift 実装のポイント

• n == Int.min のとき -n はオーバーフローで実行時エラーになります。絶対値は n.magnitude（UInt を返す）で取ると安全です。
• Double は誤差が出るので == で比較しません。テストコードは abs(a - b) < 1e-9 で判定しています。
• 再帰の深さは指数のビット数（最大 64 程度）なので、スタックあふれの心配はありません。

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        let base = n < 0 ? 1 / x : x
        return power(base, n.magnitude)
    }

    private func power(_ x: Double, _ m: UInt) -> Double {
        if m == 0 { return 1 }
        let half = power(x, m / 2)
        return m % 2 == 0 ? half * half : half * half * x
    }
}