Sqrt(x)

Easy
811.

Sqrt(x)

Sqrt(x) is an easy coding problem on math and binary search, asked in Amazon, Microsoft and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Sqrt(x) — Solution in Python, Java & C++

Sqrt(x) solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Microsoft.

Sqrt(x) is an easy coding problem on math and binary search, asked in Amazon, Microsoft and Infosys interviews.

  • 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

Hints for Sqrt(x)

  1. Hint 1

    You are looking for the largest r with r · r <= x — a monotone predicate.

  2. Hint 2

    Binary search r over [1, 46341]; anything larger squares past a 32-bit integer.

  3. Hint 3

    Compare with mid · mid <= x in a type wide enough not to overflow, or bound the range instead.

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

Java

public static int mySqrt(int x) {
    if (x < 2) return x;
    int lo = 1, hi = 46341;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if ((long) mid * mid <= x) lo = mid; else hi = mid - 1;
    }
    return lo;
}

C++

int mySqrt(int x) {
    if (x < 2) return x;
    int lo = 1, hi = 46341;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if ((long long) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search