Integer square root
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
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;}