Rust Interview Puzzles: SQRT implementation

Rust Interview Puzzles: SQRT implementation


We need to calculate the square root of a provided integer number num without using built-in functions. The result should be rounded down in case it is not a whole number.


Input numOutputExplanation
52sqrt(5) = 2.23 rounded to 2


fn sqrt(num: i32) -> i32 {
    assert!(num >= 0);

    let mut left = 0;
    let mut right = num;
    while left < right {
        let mid = (left + right + 1) / 2;
        if mid * mid > num {
            right = mid - 1;
        } else {
            left = mid;


The first idea that comes to mind could be a simple brute force like:

fn sqrt(num: i32) -> i32 {
    let mut sqrt = 1;
    while sqrt * sqrt <= num {
        sqrt += 1;
    sqrt - 1

It would work but, obviously, in terms of run-time complexity, it would not be ideal. So, instead of iterating over all numbers, we could improve the solution using Binary Search. The idea is to divide the interval of numbers by 2 to get the middle number mid and then continue the search within either the left or the right half of the interval, repeating the exercise while left < right.


The time complexity of this solution is O(lg n) (where n is the input number num). The auxiliary space complexity is O(1).

Rust Playground with this code