Implement intsqrt(int x).

Compute and return the square root ofx.

Have you met this question in a real interview?

Yes

Example

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

Challenge

O(log(x))

class Solution {

public:

/\*\*

 \* @param x: An integer

 \* @return: The sqrt of x

 \*/

int sqrt\(int x\) {

    // write your code here

    uint64\_t i = 1;

    while \(i \* i <= x\) {

        i \*= 2;

    }

    uint64\_t l = i / 2, r = i;

    while \(l + 1 < r\) {

        uint64\_t m = \(l + r\) / 2;

        uint64\_t val = m \* m;

        if \(val == x\) {

            return m;

        } else if \(val > x\) {

            r = m;   

        } else {

            l = m;

        }

    }

    if \(r \* r <= x\) {

        return r;

    }

    return l;

}

};