Implement Integer Square Root
Company: J.P. Morgan
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a non-negative integer `x`, implement `sqrt(x)` and return the integer part of its square root, i.e., `floor(sqrt(x))`.
Requirements:
- Do not use a built-in square root function or exponent operator.
- Your solution should handle large 32-bit signed integers without overflow.
- Explain the time and space complexity.
Examples:
- `x = 4` returns `2`.
- `x = 8` returns `2`, because `sqrt(8) = 2.828...` and the integer part is `2`.
Expected approach:
- First solve it using binary search.
- Follow-up: discuss whether there is a more efficient practical method, such as Newton's method, and compare it with binary search.
Quick Answer: This question evaluates numerical algorithm design and integer arithmetic competence, including robustness for edge cases and overflow handling, and is categorized in the Coding & Algorithms domain.
Given a non-negative integer `x`, implement integer square root and return the integer part of its square root, i.e., `floor(sqrt(x))`.
Requirements:
- Do NOT use any built-in square root function or the exponent/power operator.
- Handle large 32-bit signed integers without overflow (be careful with `mid * mid`).
- Explain the time and space complexity.
Examples:
- `x = 4` returns `2`.
- `x = 8` returns `2`, because `sqrt(8) = 2.828...` and the integer part is `2`.
- `x = 0` returns `0`; `x = 1` returns `1`.
Approach: Use binary search over the candidate answer range `[0, x]` (you can tighten the high bound to `x // 2` for `x >= 2`). For each `mid`, compare `mid * mid` against `x`. Follow-up: Newton's method converges faster in practice (quadratically) than binary search's logarithmic step count — worth discussing the trade-off.
Constraints
- 0 <= x <= 2147483647 (fits in a 32-bit signed integer)
- Do not use any built-in square root function or exponent/power operator
- Must not overflow: in Java/C++, compute mid * mid using a 64-bit type
Examples
Input: (4,)
Expected Output: 2
Explanation: 4 is a perfect square; floor(sqrt(4)) = 2.
Input: (8,)
Expected Output: 2
Explanation: sqrt(8) = 2.828..., integer part is 2.
Hints
- The answer lies in the range [0, x]. For x >= 2, the square root is at most x // 2, so you can search [1, x // 2].
- Binary search on the candidate answer: if mid * mid <= x, mid could be the answer (record it) and search higher; otherwise search lower.
- In languages with fixed-width integers, mid * mid can overflow 32 bits — cast to a 64-bit (long / long long) before multiplying.
- Follow-up: Newton's iteration r = (r + x // r) // 2 converges quadratically and is the more efficient practical method.