Square Root

You are given a positive integer n. Return the square root of n.

If n is not a perfect square, return the floor of its square root — the greatest integer that is less than or equal to the true square root.

In other words, find the largest integer x such that x * x <= n.

Hints

· Stuck? Reveal one nudge at a time.

You cannot use a library square-root function. What simple question can you ask each candidate integer x?

As x grows, x * x only grows. So the answers to x * x <= n look like yes, yes, yes, no, no — you want the last yes.

A sorted run of yeses followed by nos is exactly what binary search finds: probe the middle of [1, n], keep the half that can still hold the last yes, and remember the best fitting mid.

Common doubts

Two reasons. Interviews test whether you can derive it — the monotonic yes/no structure is the real lesson. And floating-point sqrt can return values like 3.9999999 for large perfect squares, so flooring it gives an off-by-one wrong answer.

Always floor. For n = 15 the true root is about 3.87, but the answer is 3 — the largest integer whose square does not exceed n — never 4.

Because when the loop ends, lo and hi have crossed and neither necessarily points at the answer. Saving ans = mid every time mid * mid <= n guarantees you return the largest value that actually fit.

Interview follow-ups

· What an interviewer asks next.

Binary search still takes only about 60 iterations. The one change: compute mid * mid in a 64-bit (or bigger) type, or rearrange the test as mid <= n / mid to avoid overflow entirely.

Yes — after the integer binary search, switch to binary search on real numbers: repeatedly halve a floating-point interval around the answer, or run Newton's method x = (x + n/x) / 2, which converges quadratically.

Any problem where feasibility is monotonic in the answer: minimum ship capacity within D days, Koko's minimum eating speed, allocating books to minimize the largest load. Binary-search the answer, test feasibility at each mid.

Fun facts

Newton's method for square roots — repeat x = (x + n/x) / 2 — was known to the Babylonians nearly 4,000 years ago, millennia before calculus formalized it.
The famous fast inverse square root hack in the Quake III engine approximated 1/sqrt(x) with a single bit-level trick and one Newton step — because calling sqrt was too slow for 1990s 3D graphics.
The yes-yes-no boundary you binary-search here is the same structure behind git bisect, which finds the commit that broke your build in O(log n) checkouts.

Asked at

AmazonMicrosoftGoogleAdobeSamsung

Frequently Sometimes Occasionally

Example 1

Input: n = 4
Output: 2
4 is a perfect square, so its square root is exactly 2.

Example 2

Input: n = 11
Output: 3
The square root of 11 is about 3.316. It is not a whole number, so we return the floor: 3.

Example 3

Input: n = 1
Output: 1
1 is a perfect square — its square root is 1.

Constraints

- 1 <= n <= 3*10^4

Computing an integer square root without calling a library function is a classic warm-up that hides a big idea: the answer lives in a sorted, invisible search space, and anything sorted can be binary-searched. Master this and you unlock a whole family of search-on-the-answer problems.

Prerequisites

Before you start

· Concepts used directly in the solution.

Monotonic functions. As x grows, x * x only grows — once a square overshoots n, every larger square overshoots too.

Binary search. Repeatedly halving a range of candidates by asking one yes/no question about the midpoint.

Floor of a number. The greatest integer less than or equal to a value — floor of 3.316 is 3.

Understand the problem

Restated plainly: find the largest integer x with x * x <= n. If n is a perfect square, x * x equals n exactly; otherwise x is the floor of the true square root.

Worked example — n = 11

x:      1    2    3    4
x*x:    1    4    9   16
             fits ✓   too big ✗
answer: 3   (3*3 = 9 <= 11, but 4*4 = 16 > 11)

Clarifying questions

Asking a few sharp questions before coding shows you think about contracts, not just code.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is n always at least 1?”

Yes — n >= 1, so the answer is always at least 1 and we never worry about zero or negatives.

“Can I use the built-in square root function?”

Interviewers almost always say no — the point is to derive it. Floating-point sqrt can also be off by one for large inputs.

Edge cases

“What should I return for n = 1?”

1 — it is a perfect square. This is the smallest input and a common off-by-one trap.

“What about a value just below a perfect square, like n = 15?”

Return 3, not 4 — we floor, never round. 4*4 = 16 > 15.

Constraints and scale

“How large can n get?”

Up to 3 * 10^4 here — even a linear scan passes, but binary search is the answer the interviewer wants, and it scales to 10^18.

The ideal opening — say it like this

Before I code, a few quick questions.

I assume n is at least 1, so the answer is always at least 1 — correct?

And when n is not a perfect square, I should floor the root, never round up — for n equals 15 the answer is 3.

Since squares grow monotonically, I will binary-search for the largest x with x squared at most n.

Key observations

1Aha

The candidates form a sorted yes-no boundary

Ask each candidate x the question: does x * x <= n? The answers look like yes, yes, yes, no, no, no… — all the yeses come first, because squaring is monotonic. Our target is the last yes.

n = 11
x:        1    2    3  |  4    5   ...
x*x<=11:  yes  yes  yes |  no   no
                    ^ last yes = answer

2Aha

A sorted boundary means binary search

Any time answers split into a yes-prefix and a no-suffix, you can find the boundary in O(log n) steps: probe the middle, keep the half that might contain the last yes, repeat. No need to test every candidate.

3Aha

Remember the best yes as you go

When mid * mid <= n, mid is a valid answer — save it and search right for a bigger one. When mid * mid > n, mid is useless — search left. The last saved value is the floor square root.

Brute force vs optimal

	Brute force	Binary search
Time	O(sqrt(n))	O(log n)
Space	O(1)	O(1)
Idea	Try sides 1, 2, 3… until one overshoots	Halve the candidate range around the yes-no boundary

Both full implementations are in the Approaches selector below.

Summary

Key takeaway

When a question about a number has yes-yes-yes-no-no answers as the candidate grows, you do not need the formula — you binary-search the boundary. This search on the answer pattern reappears everywhere: allocation problems, minimum capacity to ship packages, Koko eating bananas.

lo = 1, hi = n, ans = 1
while lo <= hi:
    mid = (lo + hi) / 2
    if mid*mid <= n:  ans = mid; lo = mid + 1   # valid — try bigger
    else:             hi = mid - 1              # too big — go smaller
return ans