Sqrt(x)
Return the integer part of the square root of a non-negative integer without a built-in square root or power function. A clean exercise in binary search on the answer. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a non-negative integer x. Return the largest integer r such that r * r ≤ x. In other words, return the square root of x rounded down to a whole number.
Don't use any built-in exponent or square root function or operator (no sqrt, pow, **, or Math.sqrt).
Example 1
- Input
- x = 25
- Output
- 5
5 × 5 = 25 exactly.
Example 2
- Input
- x = 20
- Output
- 4
The real square root is about 4.47. 4 × 4 = 16 ≤ 20, but 5 × 5 = 25 > 20.
Example 3
- Input
- x = 0
- Output
- 0
Constraints
- 0 ≤ x ≤ 2³¹ - 1
- The answer is an integer; any fractional part is dropped.
- Built-in square root and exponent functions are not allowed.
Practice
Runs 15 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Sqrt(x) in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Sqrt(x)
Pattern: Binary search on the answer
The condition r * r ≤ x is true for every r from 0 up to the answer and false for every r after it. A yes/no question that flips exactly once as r grows is the signature of binary search on the answer: you aren't searching an array, you're searching the range of possible answers.
Search r in [0, x] (or [0, x / 2 + 1] for a tighter bound). If mid * mid ≤ x, mid is a valid candidate, so remember it and look higher. Otherwise look lower. When the range is empty, the last valid candidate is the answer.
The only subtle part is overflow: in languages with 32-bit integers, mid * mid can overflow for x near 2³¹. Compare mid ≤ x / mid instead, or use a 64-bit type.
Approach 1: Linear scan
Try r = 0, 1, 2, ... and stop at the first r with (r + 1)² > x. Correct and simple, but for the largest inputs it takes about 46,000 steps where binary search needs about 31.
Time O(√x) · Space O(1)
Approach 2: Newton's method
Start with r = x and repeat r = (r + x // r) // 2 while r * r > x. Each step roughly doubles the number of correct digits, so it converges very fast. It is a great follow-up, but the stopping condition with integer division needs care.
Time O(log x), and fast in practice · Space O(1)
Approach 3: Binary search on r
- Set
lo = 0,hi = x,ans = 0. - While
lo ≤ hi: letmid = (lo + hi) // 2. Ifmid * mid ≤ x, setans = midandlo = mid + 1. Otherwise sethi = mid - 1. - Return
ans.
Each step halves the range, and ans always holds the largest value confirmed so far.
Time O(log x) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Linear scan | O(√x) | O(1) |
| Newton's method | O(log x), and fast in practice | O(1) |
| Binary search on r | O(log x) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Sqrt(x) solution in Python
def my_sqrt(x: int) -> int:
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 ansSqrt(x) solution in JavaScript
function mySqrt(x) {
let lo = 0;
let hi = x;
let ans = 0;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (mid * mid <= x) {
ans = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return ans;
}Common mistakes
- Overflow from mid * mid in a 32-bit language. Use a 64-bit type or compare mid against x / mid.
- Off-by-one at the end of the search: returning lo instead of hi (or the saved candidate) gives the ceiling instead of the floor.
- Starting with lo = 1 and forgetting that x = 0 must return 0.
- Using floating point (x ** 0.5) and truncating, which is both disallowed and can be wrong for large perfect squares due to rounding.
What interviewers look for
Say the monotonic property out loud: "r² ≤ x holds for a prefix of r values and then stops holding, so I can binary search for the boundary." That one sentence shows you recognize the pattern, which is the real skill being tested, since the same idea solves Koko Eating Bananas, capacity-to-ship, and many others.
Then be explicit about which variant of binary search you are writing and what the loop invariant is. Mention overflow even if your language doesn't have it; interviewers often ask.
Follow-up questions
How would you return the square root to a given number of decimal places?
Binary search over real numbers between 0 and max(1, x), stopping when hi - lo is below the precision you need, or run Newton's method on floats. You can also scale: the floor square root of x · 10^(2k), divided by 10^k, gives k exact decimal digits.
How would you check whether x is a perfect square?
Compute r = floor(√x) with the same binary search and check whether r * r == x. You can also binary search directly for a mid with mid * mid == x.
How does Newton's method work here and when does it stop?
Newton's method on f(r) = r² - x gives r_next = (r + x / r) / 2. Starting from r = x with integer division, the sequence decreases monotonically toward the floor of the root, so you loop while r * r > x and return r. It converges in a handful of steps even for x near 2³¹.
Companies that ask Sqrt(x)
Sqrt(x) is tagged by 103 companies in our interview dataset. The score shows how often it comes up at each company.
- Bumble100%
- Stubhub100%
- Darktrace100%
- Doximity100%
- JPMorgan Chase100%
- Baxter International100%
- Northrop Grumman100%
- Celonis100%
- Albertsons93%
- Discord91%
- Nubank90%
- Sambanova Systems89%
- Cdk Global84%
- Udacity84%
- Sift83%
- Bandwidth82%
- Project4482%
- Iterable81%
- Snorkel Ai81%
- Epic Games80%
- Zoho78.3%
- Grammarly78.3%
- Palantir78%
- Arcellx77%
and 79 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required