Integer square root

Easy

Problem

Given a non-negative integer x, return floor(√x) without using a built-in square-root function.

Example 1

Input:  x = 8
Output: 2

√8 ≈ 2.83.

Example 2

Input:  x = 16
Output: 4

Also asked as: square root of an integer

Test cases

Case 1

Input:    8
Expected: 2

Case 2

Input:    16
Expected: 4

Case 3

Input:    2147395599
Expected: 46339

Case 4

Input:    1
Expected: 1

Case 5

Input:    0
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Binary search on the answer

Time O(log x)Space O(1)

Search 0..x for the largest m with m·m ≤ x.

function isqrt(x) {
if (x < 2) return x;
let lo = 1, hi = x, ans = 1;
while (lo <= hi) {
const mid = lo + ((hi - lo) >> 1);
if (mid <= x / mid) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}
return ans;
}