PPractick

The problem

A game engine running on a microcontroller needs distances between objects, which means square roots, but the chip has no floating-point unit, and converting to double and back can also be off by one for large values. The task: compute ⌊√x⌋, the largest integer whose square doesn't exceed x, using only integer arithmetic. It's the classic first example of binary search on the answer: the answer lies in [0, x], and "does m² fit under x?" is true for small m and false for large m.

Example: x = 8 → 2 (since 2² = 4 ≤ 8 < 9 = 3²).

Function signature

int mySqrt(int x);  // floor(sqrt(x)) for x >= 0, integer arithmetic only

Test cases

Input x	Output	Explanation
4	2	Perfect square
8	2	2.828... rounded down
0	0
1	1
15	3
16	4
2147395599	46339	46340² = 2147395600 is just too big
2147483647	46340	INT_MAX: 46340² fits, 46341² doesn't

(Confirm: x ≥ 0; no floating-point functions; the result is truncated towards zero.)

How interviewers phrase it

• "Implement int sqrt(int x) without using built-in exponent functions" (LeetCode 69).
• "Check whether a number is a perfect square" (LeetCode 367), which uses the same search.
• A standard introduction to binary search on the answer.

Clarifying questions to ask

1. Should the result be rounded down?
2. Can I use sqrt from <cmath>? (Usually not.)
3. What's the range of x? (m × m can overflow 32 bits.)

Follow-ups to expect

1. "What's the monotonic predicate?"
2. "How do you avoid overflow?"
3. "Why not just (int)sqrt(x)?"
4. "What about Newton's method?"
5. "Complexity?"

Related questions

• Find Nth root of a number Medium
• Kth Missing Positive Number Easy
• Find the repeating and missing number Medium
• First and last occurrence Medium
• Search in rotated sorted array-I Medium
• Search in rotated sorted array-II Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in