69. Sqrt(x)

Description

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.

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} x
 * @return {number}
 */
let mySqrt = function(x) {
    let num = 1;
    
    while(num * num <= x){
        num++;
    }
    
    return num - 1;
};

Analysis

This is simple. We start at 1 and iterate over integers until we reach one whose square is larger than x. The running time is also simply O(sqrt(x)). To put that into perspective since O(sqrt(n)) doesn't show up as often as O(logn), O(n^2), etc. in algorithm analysis, O(sqrt(n)) ncreases more rapidly than O(logn) but significantly less than O(n).