LeetCode Sqrt(x)

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

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.

Constraints:

0 <= x <= 2^31 - 1

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;

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

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

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
}

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

Dry Run

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.