Katkat
Back

Implement Integer Square Root

J.P. MorganData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

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 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.