Integer Square Root
Problem
Given a non-negative whole number, return the largest whole number whose square does not exceed it. The fractional part is discarded rather than rounded, so a number that is not a perfect square gives the value just below its true root. Built-in square root functions are not allowed.
Examples
Input: n = 8
Output: 2
Why: 2 squared is 4 and 3 squared is 9, so the answer is cut down to 2Input: n = 16
Output: 4
Why: a perfect square returns its exact rootInput: n = 0
Output: 0
Why: edge case, zero is its own rootHints
0 / 3
Trying every candidate from one upwards works but takes far too many steps for a large input. Notice how the answer relates to the candidates around it.
Squaring is increasing, so every candidate below the answer passes the test and every candidate above it fails. The candidates split cleanly into a passing block and a failing block.
Search the range from zero to the number itself. Test the middle candidate by squaring it: if the square fits, remember the candidate and keep looking in the upper part, otherwise discard it and the whole upper part. The last remembered candidate is the answer.
Solution
The test does my square fit is monotone: it holds for every candidate up to the answer and fails for every candidate beyond it, which is exactly the structure a halving search needs. Each round squares the middle candidate and throws away half the range, remembering the candidate whenever it passes so the final answer survives. Comparing squares rather than taking a root keeps everything in whole numbers. Time is O(log n), and space is O(1).
def integer_sqrt(n):
low, high, best = 0, n, 0
while low <= high:
mid = (low + high) // 2
if mid * mid <= n: # mid fits, but something larger might too
best, low = mid, mid + 1
else:
high = mid - 1 # mid is too big, and so is everything above
return best
print(integer_sqrt(8)) # -> 2
print(integer_sqrt(16)) # -> 4
print(integer_sqrt(0)) # -> 0Stuck on the idea rather than the code? Binary Search covers it.