{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Sqrt(x) – Solution & Complexity

Interview solutions
/
Sqrt(x)

Solution Walkthrough

  1. Step 1: Understand the Pattern

    • We want the largest r with r * r <= x.
    • The answer is monotonic: if r * r <= x, then every smaller value also qualifies.
    • Monotonicity is exactly what binary search exploits.

  2. Step 2: Handle the Small Cases

    • For x < 2, the integer square root equals x itself (0 -> 0, 1 -> 1).
    • Returning early avoids an empty search range.
    def my_sqrt(x):
    if x < 2:
        return x

  3. Step 3: Binary Search the Root

    • Search the range [1, x] for the largest mid whose square is <= x.
    • Move the lower bound up when mid * mid <= x, otherwise move the upper bound down.
    • Track the best valid mid as you go.
    def my_sqrt(x):
    if x < 2:
        return x
    low, high, ans = 1, x, 0
    while low <= high:
        mid = (low + high) // 2
        if mid * mid <= x:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

  4. Step 4: Final Solution and Complexity

    • The search halves the range each step, so time is O(log x).
    • Space is O(1).
    • In fixed-width languages, compare mid to x // mid to dodge mid * mid overflow.
    def my_sqrt(x: int) -> int:
    if x < 2:
        return x
    low, high, ans = 1, x, 0
    while low <= high:
        mid = (low + high) // 2
        if mid * mid <= x:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

FAQ

See also

Practice Sqrt(x) online (run code in the browser)Add Two Numbers solution (medium)Binary Search solution (easy)Climbing Stairs solution (easy)Count Primes solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?