Square root of a number

JavaView on GFG

Intuition

Integer square root (floor). Binary search in range [1, n].

Algorithm

1Binary search: if mid*mid == n: return mid. If mid*mid < n: ans=mid, lo=mid+1. Else hi=mid-1.

Common Pitfalls

•Use long to avoid overflow in mid*mid. Same as LC 69. Return floor value.

Square root of a number.java

Java

// Approach: Binary search on [0, n]. Find largest x where x*x <= n.
// Time: O(log n) Space: O(1)
class Solution {
    long floorSqrt(long n) {
        if (n == 0 || n == 1)
            return n;

        long start = 1, end = n, ans = 0;

        while (start <= end) {
            long mid = (start + end) / 2;

            if (mid <= (n / mid)) {
                ans = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return ans;
    }
}

Was this solution helpful?