Integer Square Root

Problem

Given a non-negative integer x, return the integer part of its square root (i.e. floor of √x). Without using built-in pow / sqrt.

Constraints

• 0 ≤ x ≤ 2³¹ − 1

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

class Solution:
    def mySqrt(self, x):
        lo, hi, ans = 0, x, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= x:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

Java

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

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.