DEV Community

loading...

LeetCode Sqrt(x)

Alkesh Ghorpade
Ruby on Rails and Golang consultant
Originally published at alkeshghorpade.me ・3 min read

Container

Problem statement

Given a non-negative integer x, compute and return the square root of x.

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

Note: You are not allowed to use any built-in exponent function or operator, such as
pow(x, 0.5) or x ** 0.5.

Problem statement taken from: https://leetcode.com/problems/sqrtx

Example 1:

Input: x = 4
Output: 2
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.
Enter fullscreen mode Exit fullscreen mode

Constraints:

0 <= x <= 2^31 - 1
Enter fullscreen mode Exit fullscreen mode

Explanation

Brute force

The simple approach to this problem is to try with all-natural numbers starting from 1.
We continue increasing the number till the square of the number is greater than x.

C++ snippet of the above approach will look like this:

int i = 1, result = 1;

while (result <= x)
{
    i++;
    result = i * i;
}

return i - 1;
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(√ n), since we are running
a loop from 1 till the square root of that number.

The algorithm can still be improved by using the binary search concept here.

Binary search

Since the value of i*i i.e., square of numbers increasing monotonically,
we can use this concept to find the square root of the number using
binary search.

Let's check the algorithm below:

- return x if x <= 1
- initialize start = 2, end = x, middle = 0

- Loop while start <= end
  - middle = start + ( end - start )/ 2
  - if middle == x / middle
    - return middle

  - if middle < x / middle
    - set start = middle + 1
  - else
    - set end = middle - 1

- if start > x /start
  - return start - 1

- return start
Enter fullscreen mode Exit fullscreen mode

The time complexity of the above approach is O(log(n))

C++ solution
class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1){
            return x;
        }

        int start = 2, end = x, middle;

        while(start <= end){
            middle = start + (end - start)/2;

            if(middle == x/middle){
                return middle;
            }

            if(middle < x/middle){
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }

        if(start > x/start){
            return start - 1;
        }

        return start;
    }
};
Enter fullscreen mode Exit fullscreen mode
Golang solution
func mySqrt(x int) int {
    start := 0
    end := x

    for start <= end {
        middle := start + ( end - start )/2
        if middle * middle > x {
            end = middle - 1
        } else if (middle + 1)*( middle + 1) > x {
            return middle
        } else {
            start = middle + 1
        }
    }

    return start
}
Enter fullscreen mode Exit fullscreen mode
Javascript solution
var mySqrt = function(x) {
    let start = 0, end = x, middle = 0;

    while (start < end) {
        middle = parseInt((start + end)/2);
        if (middle * middle === x) {
            return middle;
        }
        if (x < middle * middle) {
            end = middle - 1;
        } else {
            start = middle + 1;
        }
    }

    return x < end * end ? end - 1 : end;
};
Enter fullscreen mode Exit fullscreen mode

Let's dry-run our algorithm to see how the solution works.

x = 8

Step 1: x <= 1
        8 <= 1
        false

Step 2: start = 2
        end = 8

Step 3: Loop while 2 <= 8
        true

        middle = 2 + (8 - 2) / 2
               = 2 + 6 / 2
               = 2 + 3
               = 5

        middle == x / middle
        5 == 8 / 5
        5 == 1
        false

        middle < x/middle
        5 < 8 / 5
        5 < 1
        false

        end = middle - 1
        end = 5 - 1
        end = 4

Step 4: Loop while 2 <= 4
        true

        middle = 2 + (4 - 2) / 2
               = 2 + 2 / 2
               = 2 + 1
               = 3

        middle == x / middle
        3 == 8 / 3
        3 == 2
        false

        middle < x/middle
        3 < 8 / 3
        3 < 2
        false

        end = middle - 1
        end = 3 - 1
        end = 2

Step 4: Loop while 2 <= 2
        true

        middle = 2 + (2 - 2) / 2
               = 2 + 0 / 2
               = 2 + 0
               = 2

        middle == x / middle
        2 == 8 / 2
        2 == 4
        false

        middle < x/middle
        2 < 8 / 2
        2 < 4
        true

        start = middle + 1
        start = 2 + 1
        start = 3

Step 5: Loop while 3 <= 2
        false

Step 6: if start > x/start
        3 > 8 / 3
        3 > 2

        return start - 1

So the answer is 2.
Enter fullscreen mode Exit fullscreen mode

Discussion (0)