{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Sqrt(x) – Solution & Complexity

Interview solutions
/
Sqrt(x)

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. 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. 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. 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)Binary Search solution (easy)Climbing Stairs solution (easy)Count Primes solution (medium)Excel Sheet Column Number solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?