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\).