75. Integer Square Root

Given a non-negative integer n, find floor(sqrt(n)) - the largest integer whose square is less than or equal to n - without using a built-in square root function.

Input: A single line containing the integer n. Output: Print a single integer - floor(sqrt(n)).

0 <= n <= 2*10^9

This is a foundational example of 'binary search on the answer' (searching over a range of POSSIBLE ANSWERS rather than array indices) - a pattern reused constantly across many of this category's harder problems (wood cutting, book allocation, aggressive cows, and more).

Find the largest whole number whose square is still less than or equal to a given number, without using any built-in square root function. Brute force: Try every integer starting from 0 upward, squaring each and checking against n, stopping the moment the square exceeds n - this costs O(sqrt(n)), which can still be slow for n up to 2*10^9 (around 44,721 iterations, actually quite fast, but binary search is the more scalable, elegant pattern to reach for). Optimised: Since 'mid*mid <= n' becomes false in a perfectly monotonic way as mid increases (once it flips to false, it stays false for all larger mid), binary searching directly on the ANSWER value (not on an array) finds the exact boundary in O(log n) - a classic 'binary search on the answer' pattern rather than searching within a given array.

Start with an initial guess x (for example, n itself or a rough estimate), and repeatedly refine it using the Newton-Raphson update x = (x + n/x) / 2 using integer division, which converges toward sqrt(n) quadratically - each iteration roughly doubles the number of correct digits. Stop once x*x <= n but (x+1)*(x+1) > n. While binary search already runs in logarithmic time, Newton's method's quadratic convergence typically reaches the answer in noticeably fewer iterations in practice for the same input size, making it the technique of choice when performance matters most. Time: O(log n) Space: O(1)

Starting from 0, try successive integers 0, 1, 2, and so on, squaring each one, until the square exceeds n; the previous integer (the last one whose square did not exceed n) is floor(sqrt(n)). This is correct and simple, but for n up to 2*10^9 the answer can be around 44,721, so it may need tens of thousands of iterations in the worst case. Time: O(sqrt n) Space: O(1)

Binary search over the candidate answer in the range [0, n]: at each step check whether mid*mid <= n, moving the search range up if so (mid could still be too small) or down otherwise, keeping track of the largest mid whose square doesn't exceed n. Because each step halves the remaining search space rather than trying every candidate sequentially, this finds the answer in a logarithmic number of steps instead of a square-root number, which is a substantial improvement for the large values of n allowed here. Time: O(log n) Space: O(1)

1. Binary search over the ANSWER itself, in the range [0, n]. 2. For a candidate mid value, check if mid*mid <= n. 3. If it does, this mid might still be too small - remember it as a candidate and search the upper half for something bigger that still qualifies; if mid*mid is too big, search the lower half.

Time: O(log n) - a standard binary search over the range [0, n]. Space: O(1) - just a few pointer variables.

Test n = 0, n a perfect square, and n = 2*10^9 (largest case, watch for overflow when squaring the candidate).

Be ready to explicitly mention the overflow risk when squaring a large mid value (especially in languages with fixed-size integers) - using a wider integer type or checking mid <= n/mid instead of mid*mid <= n avoids this.