README.md

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Solutions (Rust)

1. Brute Force

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut n = 1;
        while n <= x / n {
            n += 1;
        }
        n - 1
    }
}

2. Binary Search

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 || x == 1 {
            return x;
        }
        let mut left = 0;
        let mut right = x;
        let mut mid = (left + right) / 2;
        loop {
            if mid <= x / mid && (mid + 1) > x / (mid + 1) {
                return mid;
            } else if mid > x / mid {
                right = mid;
            } else if mid < x / mid {
                left = mid;
            }
            mid = (left + right) / 2;
        }
    }
}

3. (n + 1)² = n² + 2n + 1

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        let mut n = 0;
        let mut x = x - 1;
        while x >= 0 {
            n += 1;
            x -= 2 * n + 1;
        }
        n
    }
}

4. Newton's Method

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 {
            return 0;
        }
        let x = x as usize;
        let mut n = x;
        while n > x / n {
            n = (n + x / n) / 2;
        }
        n as i32
    }
}