Quick Overview

Implement a square-root routine based on Newton's method that returns the integer square root of a non-negative 32-bit integer, the largest value whose square does not exceed the input, without calling library square-root or power functions. It tests numerical iteration, termination conditions and exact integer arithmetic.

Integer Square Root with Newton's Method and No Library Calls

Company: Goldman Sachs

Role: Quantitative Researcher

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a square-root routine based on Newton's method. To give the result a unique, exactly checkable value, the function returns the integer square root of a non-negative integer: the largest integer whose square does not exceed the input. ### Function Signature ```python def newton_isqrt(x: int) -> int: ``` `x` is the non-negative integer whose square root is required. ### Rules - Return the largest integer `r >= 0` such that `r * r <= x`, that is, the square root of `x` rounded down. - The interviewer asked for the root to be computed with Newton's method. Do not call a library routine that computes square roots, powers or logarithms, such as `math.sqrt`, `math.isqrt`, `math.pow`, `math.log` or `x ** 0.5`. ### Constraints - `0 <= x <= 2^31 - 1` - The answer is at most 46340, but squaring a value just above it exceeds `2^31 - 1`. Python integers do not overflow; in a fixed-width language this needs care. ### Examples **Example 1** ```text Input: x = 8 Output: 2 ``` 2 × 2 = 4 does not exceed 8, but 3 × 3 = 9 does. **Example 2** ```text Input: x = 49 Output: 7 ``` 49 is a perfect square, so its exact root 7 is returned. **Example 3** ```text Input: x = 2147483647 Output: 46340 ``` 46340 × 46340 = 2147395600 does not exceed the input, while 46341 × 46341 = 2147488281 does.

Overview: Implement a square-root routine based on Newton's method that returns the integer square root of a non-negative 32-bit integer, the largest value whose square does not exceed the input, without calling library square-root or power functions. It tests numerical iteration, termination conditions and exact integer arithmetic.

Read the full Goldman Sachs Quantitative Researcher interview experience this question came from

Implement a square-root routine based on Newton's method. To give the result a unique, exactly checkable value, the function returns the integer square root of a non-negative integer. Given a non-negative integer `x`, return the largest integer `r >= 0` such that `r * r <= x`, that is, the square root of `x` rounded down. The root must be computed with Newton's method. Do not call a library routine that computes square roots, powers or logarithms, such as `math.sqrt`, `math.isqrt`, `math.pow`, `math.log` or `x ** 0.5` (or their equivalents in other languages). ### Function `newton_isqrt(x)` takes the integer `x` and returns the integer `r`. ### Constraints - `0 <= x <= 2^31 - 1` - The input and the answer fit in a signed 32-bit integer (the answer is at most 46340), but squaring a value just above the answer exceeds `2^31 - 1` (46341 × 46341 = 2147488281). Python integers do not overflow; in fixed-width languages such as Java and C++, intermediate products and sums need 64-bit arithmetic. ### Examples **Example 1** ```text Input: x = 8 Output: 2 ``` 2 × 2 = 4 does not exceed 8, but 3 × 3 = 9 does. **Example 2** ```text Input: x = 2147483647 Output: 46340 ``` 46340 × 46340 = 2147395600 does not exceed the input, while 46341 × 46341 = 2147488281 does.

Constraints

  • 0 <= x <= 2^31 - 1
  • The answer is at most 46340, but squaring a value just above it exceeds 2^31 - 1 (46341 × 46341 = 2147488281); fixed-width languages need 64-bit intermediate arithmetic.
  • Compute the root with Newton's method; do not call a library routine that computes square roots, powers or logarithms (such as math.sqrt, math.isqrt, math.pow, math.log or x ** 0.5).

Examples

Input: (0,)

Expected Output: 0

Explanation: Minimum valid input: 0 * 0 = 0, so the root of 0 is 0 (an implementation must not divide by zero).

Input: (1,)

Expected Output: 1

Explanation: Root equals the input: 1 * 1 = 1 <= 1 and 2 * 2 = 4 > 1; catches a search capped at x / 2.

Hints

  1. The answer r is the unique non-negative integer with r * r <= x < (r + 1) * (r + 1).
  2. The interviewer asked for Newton's method: think about how to refine a guess for the root using only integer arithmetic, and about a stopping rule that cannot loop forever.
  3. Squares of values near 46341, and sums near 2^31, exceed the signed 32-bit range; in Java and C++ keep intermediate arithmetic in a wider type.

Loading coding console...

Show the approach

Approach

Integer Newton iteration. If x < 2 the answer is x itself (0 or 1), which also avoids dividing by zero. Otherwise start from the guess r = x, which is at least the true root s = floor(sqrt(x)), and repeatedly compute y = floor((r + floor(x / r)) / 2), stopping as soon as y is not smaller than r; then return r. Invariant: every guess satisfies r >= s. Because r is an integer, floor((r + floor(x / r)) / 2) equals floor((r + x / r) / 2), and by the AM-GM inequality (r + x / r) / 2 >= sqrt(x), so every new guess y is still >= s. While r > s we have r * r > x, so x / r < r and therefore y < r: the guesses strictly decrease and the loop terminates. When r = s, x / s >= s gives y >= s = r, so the loop stops exactly at s, the largest integer whose square does not exceed x. Stopping on y >= r (rather than waiting for y == r) avoids the two-cycle between k - 1 and k that occurs for x = k * k - 1 (for example 8, 15, 24). Edge cases: x = 0 and x = 1 return immediately; the largest input 2147483647 gives 46340. In Java and C++ the sum r + x / r reaches 2^31 on the first step when x = 2^31 - 1, so the iteration runs in 64-bit integers; JavaScript numbers represent these values exactly, and flooring a quotient of integers below 2^53 is exact. The guess roughly halves while it is far above the root and then converges quadratically, so the loop runs O(log x) times.

Time complexity:
O(log x)
Space complexity:
O(1)