Sqrt(x)

Notes.md

Question: 69. Sqrt(x)

Intution:

Time Complexity: $$O(log(n))$$

Space Complexity: $$O(1)$$

Solution:

class Solution {
    public int mySqrt(int x) {
        long low = 1;
        long high = x;
        long mid = -1;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (mid * mid == x) return (int) mid;
            else if (mid * mid < x) low = mid + 1;
            else high = mid - 1;
        }
        return (int) high;
    }
}