[−][src]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 } }