Function leetcode_for_rust::cd0069_sqrtx::my_sqrt

pub fn my_sqrt(x: i32) -> i32

Solutions for i32

Approach 1: Binary Search

• Time complexity: log(n)

• Space complexity: log(n)

• Runtime: 0 ms

• Memory: 2.4 MB

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 || x == 1 { return x; }

        let mut left = 1;
        let mut right = x;
        let mut res = 1;

        while left <= right {
            let mid = (right - left) / 2 + left;
            if x / mid == mid { return mid; };
            if mid > x / mid {
                right = mid - 1;
            } else {
                left = mid + 1;
                res = mid;
            }
        }
        res
    }
}

Approach 2: Newton's Method

• Time complexity: 𝑙𝑜𝑔2(𝑁)

• Space complexity:

• Runtime: 0 ms

• Memory: 2.4 MB

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 { return x; }

        let x = x as usize;
        let mut r = x;
        while r > x / r {
            r = (r + x / r) / 2;
        }
        r as i32
    }
}

Approach 3: Lomont's Paper

• Time complexity:

• Space complexity:

• Runtime: 0 ms

• Memory: 2.4 MB

use::std::mem;

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut n = x as f64;
        let half = 0.5 * n;
        let mut i = unsafe {
            std::mem::transmute::<f64, i64>(n)
        };
        i = 0x5fe6ec85e7de30da - (i>>1);
        n = unsafe{
            std::mem::transmute::<i64, f64>(i)
        };
        for _i in 0..3 {
            n = n * (1.5 - half * n * n);
        }
        (1.0 / n) as i32
    }
}