50.powx-n.md

問題

https://leetcode.com/problems/powx-n/

回答

初回の回答:

これは $\mathcal{O}(\log{_2}n)$ で計算できない実装のため、タイムアウトしてしまった。$2^{31}-1$ 乗する場合、単純に $2^{31}-1$ 回計算することになってしまう。

impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        let mut x = x;
        if let 0 = n {
            return 1.0;
        };
        let i = x;
        for _ in 1..(n).abs() {
            x *= i;
        }
        if n > 0 {
            return x;
        } else {
            return 1.0 / x;
        }
    }
}

二回目の回答:

impl Solution {
    pub fn my_pow(x: f64, n: i32) -> f64 {
        let result = Self::pow_recursive(x, n);
        if n < 0 {
            return 1.0 / result;
        } else {
            return result;
        }
    }

    fn pow_recursive(x: f64, n: i32) -> f64 {
        if n == 0 {
            return 1.0;
        };

        let half = Self::pow_recursive(x, n / 2);
        if n % 2 == 0 {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}