UIREADY.dev
Integer Square RootLoading saved progress…

Integer Square Root

The integer square root of a non-negative number n is the largest integer k whose square is at most n — in other words, the floor of the real square root, Math.floor(Math.sqrt(n)). So integerSqrt(16) is 4, and integerSqrt(8) is also 2 because 2 * 2 = 4 fits under 8 but 3 * 3 = 9 does not. Your job is to compute it without Math.sqrt, using either Newton's method on integers or a binary search. This is the classic Sqrt(x) interview problem.

Signature

integerSqrt(n)  // n: a non-negative integer -> floor(sqrt(n)); negative n -> NaN

Examples

integerSqrt(16); // 4    (4 * 4 === 16)
integerSqrt(8);  // 2    (2*2=4 <= 8 < 9=3*3)
integerSqrt(99); // 9    (9*9=81 <= 99 < 100)
integerSqrt(0);  // 0
integerSqrt(1);  // 1
integerSqrt(1000000); // 1000
integerSqrt(-4);      // NaN

Notes

  • Floor, not round — you want the largest k with k * k <= n, so integerSqrt(8) is 2, not 3. A perfect square returns its exact root.
  • No Math.sqrt — implement it yourself. Reaching for Math.sqrt(n) | 0 is off-limits here, and it is also quietly wrong for some large perfect squares: floating-point rounding can nudge the result just under the integer, giving an answer one too low.
  • Negative input — a negative number has no real square root. Return NaN (the test checks with Number.isNaN).
  • Base cases — 0 and 1 are their own square roots. Handle them before dividing by your guess, since dividing by zero would break Newton's method.
  • Range — assume n is a safe integer (below 2 ** 53); you do not need BigInt for arbitrarily large inputs.

FAQ

What is the time complexity?
Newton's method converges quadratically — roughly doubling the number of correct digits each step — so it finishes in about log(n) iterations, a few dozen even for enormous n. The naive linear scan is O(sqrt n), which is a million iterations near a trillion.
Why not just floor Math.sqrt(n)?
Two reasons. The exercise is to implement it without the built-in, and Math.floor(Math.sqrt(n)) can be off by one for some large perfect squares: Math.sqrt returns a float, and rounding can nudge an exact square just under the integer, so flooring gives an answer one too low.
How does it return the floor and not round up?
The integer Newton iteration starts above the true root and decreases, stopping the moment the next estimate is no longer smaller. That stopping point is the largest k with k*k <= n, which is exactly floor(sqrt(n)) — never the rounded-up value.
Loading editor…