Follow

Follow

# Rust Interview Puzzles: SQRT implementation

go4fun.fun
·Dec 22, 2022·

### Problem

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.

#### Examples:

 Input `num` Output Explanation `4` `2` `16` `4` `225` `15` `5` `2` `sqrt(5) = 2.23` rounded to `2`

### Solution

``````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;
}
}
right
}
``````

### Explanation

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`.

### Complexity

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