[/dsa/leetcode]

69 - Sqrt(x)

Tuesday, 15 September 2026

<easy> [problem]

Binary search over [0, x] for the largest integer whose square does not exceed x.

{math}{binary search}

Problem

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in C++ or x ** 0.5 in Python.
Input: x = 4
Output: 2

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

  • 0 <= x <= 2^31 - 1

Approach

floor(sqrt(x)) is the largest integer r with r * r <= x. The squares 0, 1, 4, 9, ... only go up, so the check r * r <= x is true for every r up to the answer and false for every r after it. Both approaches look for that last r where the check is still true.

One thing to watch in both: x can be as large as 2^31 - 1, whose root is 46340. The next candidate is 46341, and 46341 * 46341 = 2147488281 is larger than INT_MAX. Squaring it in an int overflows, so we do the multiplication in 64 bits.

Linear Scan

Start at i = 0 and keep stepping forward while the next number’s square still fits under x. When (i + 1) * (i + 1) goes past x, i is the answer. Checking one step ahead means we stop on the right number and don’t need to step back afterwards.

class Solution {
public:
    int mySqrt(int x) {
        long long i = 0;
        while ((i + 1) * (i + 1) <= x) {
            i++;
        }
        return i;
    }
};
  • time: O(sqrt(x)) — the loop runs once for each integer up to the answer
  • space: O(1)

Binary Search

Because the check goes from true to false at exactly one point, we can binary search over [0, x] instead of walking up one at a time. Let l = 0 and r = x. Look at mid:

  • mid * mid == x: mid is the exact root, return it.
  • mid * mid < x: mid is small enough but might not be the largest, so the answer is mid or higher. Set l = mid + 1.
  • mid * mid > x: mid is too big, and so is everything above it. Set r = mid - 1.
x = 8
l = 0, r = 8  ->  mid = 4, 16 > 8  ->  r = 3
l = 0, r = 3  ->  mid = 1,  1 < 8  ->  l = 2
l = 2, r = 3  ->  mid = 2,  4 < 8  ->  l = 3
l = 3, r = 3  ->  mid = 3,  9 > 8  ->  r = 2
l = 3, r = 2  ->  stop, return r = 2

x = 0 needs no special case. The first mid is 0, and 0 * 0 == 0 returns right away.

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l <= r) {
            long long mid = l + (r - l) / 2;
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
};
  • time: O(log x) - the search range [0, x] halves every iteration
  • space: O(1)
quantinium © 2026