1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100

//! Pow(x, n) [leetcode: powx_n](https://leetcode.com/problems/powx-n/)
//!
//! Implement `pow(x, n)`, which calculates x raised to the power n (xn).
//!
//! ***Example1:***
//!
//! ```
//! Input: 2.00000, 10
//! Output: 1024.00000
//! ```
//!
//! ***Example2:***
//!
//! ```
//! Input: 2.10000, 3
//! Output: 9.26100
//! ```
//!
//! ***Example3:***
//!
//! ```
//! Input: 2.00000, -2
//! Output: 0.25000
//! Explanation: 2-2 = 1/22 = 1/4 = 0.25
//! ```
//!
//! ***Note:***
//!
//! * -100.0 < x < 100.0
//! * n is a 32-bit signed integer, within the range [−231, 231 − 1]

/// # Solutions
///
/// # Approach 1: Iteration
///
/// * Time complexity: O(logn)
///
/// * Space complexity: O(1)
///
/// * Runtime: 0 ms
/// * Memory: 2.4 MB
///
/// ```rust
/// impl Solution {
///     pub fn my_pow(x: f64, n: i32) -> f64 {
///         let mut ln = n as i64;
///         let mut pow = 1f64;
///         let mut current = x;
///
///         if ln < 0 {
///             current = 1f64 / current;
///             ln = -ln;
///         }
///
///         while ln > 0 {
///             if ln & 1 == 1 { pow *= current; }
///             current *= current;
///             ln >>= 1;
///         }
///         pow
///     }
/// }
/// ```
///
/// # Approach 2: Recursion
///
/// * Time complexity: O(logn)
///
/// * Space complexity: O(1)
///
/// ```rust
/// impl Solution {
///     pub fn my_pow(mut x: f64, mut n: i64) -> f64 {
///         if n < 0 {
///             x = 1.0 / x;
///             n = -n;
///         }
///         if n == 0 { return 1.0; }
///         let half = my_pow(x, n/2);
///         if n & 1 == 0 {
///             return half * half;
///         } else {
///             return half * half * x;
///         }
///     }
/// }
///
pub fn my_pow(mut x: f64, mut n: i64) -> f64 {
    if n < 0 {
        x = 1.0 / x;
        n = -n;
    }
    if n == 0 { return 1.0; }
    let half = my_pow(x, n/2);
    if n & 1 == 0 {
        return half * half;
    } else {
        return half * half * x;
    }
}