Sqrtx

Problem

Solution

Finding the square root of $x$ is equivalent to finding $y$ such that $y^{2} = x$ . We can use binary search to find $y$ in the range $[0, \sqrt{2^{32} - 1}] \approx [0, 2^{16}]$ . After narrowing the range of possible square roots to within 1, within 1, we return the beginning of the range.

Code

https://github.com/GeorgeRPu/tech-interview-prep/blob/main/solutions/Sqrtx.py

def mySqrt(x: int) -> int:
    """Finds the largest integer :math:`y` such that :math:`y^2 \\leq x`.
    """
    start = 0
    end = 65536
    while start + 1 < end:
        mid = (start + end) // 2
        if mid**2 > x:
            end = mid
        else:
            start = mid

    return start

Test

>>> from Sqrtx import mySqrt
>>> mySqrt(4)
2
>>> mySqrt(8)
2

Functions

mySqrt(x)

Finds the largest integer $y$ such that $y^{2} \leq x$ .