EasyMathBinary SearchNewton's MethodUpdated Sep 2026

69. Sqrt(x)

Asked at Google, Bloomberg

Difficulty

Easy

Time

O(log x)

Space

O(1)

Pattern

Math

Companies

2

Problem

You are given a non-negative integer x. Return the integer part of its square root — that is, the largest integer r such that r * r <= x.

For example, the square root of 8 is about 2.828, so the answer is 2. The answer is never negative, and x = 0 gives 0.

You may not use any built-in power or square-root function (no pow(x, 0.5), no x ** 0.5, no math.sqrt). You have to compute the value yourself.

Find the largest r with r*r <= x

candidates01234012342*2 = 4 fits inside 8, but 3*3 = 9 is too big, so theanswer is 2
For x = 8 we want the last integer whose square does not pass 8, which is 2.

Constraints

  • ●0 <= x <= 2^31 - 1
  • ●Do not use any built-in exponent or square-root function

Examples

Example 1
Inputx = 4
Output2
Why2 * 2 = 4 exactly, so the integer part of the square root is 2.
Example 2
Inputx = 8
Output2
Why2 * 2 = 4 is <= 8, but 3 * 3 = 9 is > 8. So the largest integer whose square fits is 2.
Example 3
Inputx = 0
Output0
Why0 * 0 = 0, so the answer is 0.

Asked At

2 companies
CompanyDifficulty
GoogleEasyView all Google questions →
BloombergEasyView all Bloomberg questions →

How to Think About It

1

Brute force: iterate from 1 to x and check if i*i equals x.

2

If i*i > x, then i-1 is the answer. This is O(sqrt(x)) time.

3

Binary search on the range [1, x/2+1] to find the largest integer whose square is <= x.

4

For each mid, compare mid*mid with x to decide whether to go left or right.

5

Optimal: use binary search in O(log x) time and O(1) space.

Optimal Approach

Use binary search on the range [0, x]. For each mid, compute midmid. If midmid == x, return mid. If midmid > x, search left; otherwise search right. The answer is the last mid where midmid <= x. This runs in O(log x) time and O(1) space.

Binary search on [1, x//2]

rangelo=1, hi=412340123Start with x = 8, so the search range is 1 to 4rangelo=1, hi=212340123mid = 2 gives 4 < 8, so move lo up and keep the righthalfrange12340123hi=2mid = 2 gives 4 < 8 again, lo becomes 3 and the loopstops with hi = 2if mid*mid == x: return midif mid*mid < x: lo = mid + 1else: hi = mid - 1answer = hi
Each step throws away half of the range by comparing mid*mid with x.
ComplexityTime O(log x)Space O(1)Binary search halves the search range on every step, and only a few integer variables are kept.

What Trips People Up in Real Interviews

1

Edge cases: x = 0 returns 0, x = 1 returns 1.

2

Watch for integer overflow: use long long for mid*mid comparison.

3

The answer is the largest integer r such that r*r <= x.

4

Newton's method is an alternative that converges faster in practice.

5

Clarify with interviewer whether x is always non-negative.

Solution Code

O(log x) time
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        lo, hi = 1, x // 2
        while lo <= hi:
            mid = (lo + hi) // 2
            sq = mid * mid
            if sq == x:
                return mid
            elif sq < x:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Sqrt(x) problem?

Implement the sqrt(x) function that computes and returns the square root of a non-negative integer x. The return type is integer, so you must return the integer part of the square root. For example, sqrt(8) returns 2, not 2.828.

How do you solve Sqrt(x)?

The optimal approach runs in O(log x) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Sqrt(x)?

Sqrt(x) is asked at Google, Bloomberg. It is a easy difficulty problem.

What are common mistakes on Sqrt(x)?
  • Edge cases: x = 0 returns 0, x = 1 returns 1.
  • Watch for integer overflow: use long long for mid*mid comparison.
  • The answer is the largest integer r such that r*r <= x.
  • Newton's method is an alternative that converges faster in practice.
  • Clarify with interviewer whether x is always non-negative.