Get started

Sqrt(x) — Easy Problem & Solution

Return the square root of the non-negative integer x, rounded down to the nearest integer. You may not use any built-in exponent or square-root function.

  • Difficulty: Easy
  • Topics: Math, Binary Search
  • Asked at: Amazon, Microsoft, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the square root of the non-negative integer x, rounded down to the nearest integer.

You may not use any built-in exponent or square-root function.

Example 1

Input: x = 4
Output: 2

Example 2

Input: x = 8
Output: 2
Explanation: The true root is about 2.828, which floors to 2.

Example 3

Input: x = 2147395600
Output: 46340
Explanation: The largest perfect square inside a 32-bit int.

Constraints

  • 0 <= x <= 2147483647

How to solve Sqrt(x)

The predicate r · r <= x is true for a prefix of the candidate roots and false after, so binary search finds the boundary. Capping the range at 46341 keeps mid · mid inside a 32-bit integer.

Approach

  1. Return x directly for x < 2.
  2. Search [1, 46341] for the largest mid with mid · mid <= x, using the upper-biased midpoint (lo + hi + 1) / 2.
  3. Return lo.

Why it works

46340² = 2147395600 fits a signed 32-bit integer while 46341² = 2147488281 does not, so the search never evaluates an overflowing product. The upper-biased midpoint is what makes the 'largest satisfying value' loop terminate — with the usual (lo + hi) / 2 it would spin when hi == lo + 1.

Complexity

  • Time — O(log x)
  • Space — O(1)

Pitfalls

  • mid · mid overflows a 32-bit int for mid above 46340 — either widen the type or cap the range as here.
  • Using the plain midpoint with lo = mid loops forever.
  • Floating-point sqrt can round the wrong way near a perfect square, and the problem forbids it anyway.

Reference solution

Python

def mySqrt(x: int) -> int:
    if x < 2:
        return x
    lo, hi = 1, 46341
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo

JavaScript

var mySqrt = function(x) {
    if (x < 2) return x;
    var lo = 1, hi = 46341;
    while (lo < hi) {
        var mid = (lo + hi + 1) >> 1;
        if (mid * mid <= x) lo = mid; else hi = mid - 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue