thesarfo

Reference

Square Root (Floor Value)

Finding floor(sqrt(n)) with linear search vs. binary search, exploiting that squaring increases monotonically.

views 0

Find floor(sqrt(n)) — the greatest integer whose square doesn’t exceed n.

Brute force: loop i from 1 upward, tracking the last i where i*i <= n.

int ans = 1;


for (int i = 1; i <= n; i++) {
    if (i * i <= n) {
        ans = i;
    } else {
        break;
    }
}
return ans;

Optimal — binary search: squaring increases monotonically, so once mid*mid > n, everything larger also fails — a classic “valid until a point, then invalid” pattern.

class Solution {
    int floorSqrt(int n) {
        int low = 1, high = n;
        int ans = 1;


        while (low <= high) {
            int mid = (low + high) / 2;


            if (mid * mid > n) {
                high = mid - 1;
            } else {
                ans = mid;
                low = mid + 1;
            }
        }
        return ans;
    }
}