Square root

Problem Link

Square-root

Problem Statement

Given a positive integer n, find the square root of n.

If n is not a perfect square, return the floor value of the square root (i.e., the largest integer x such that x * x <= n).

Examples

• Input: n = 4
  Output: 2
  Explanation: 4 is a perfect square. Its square root is 2.

• Input: n = 11
  Output: 3
  Explanation: 11 is not a perfect square. Floor of √11 is 3.

• Input: n = 1
  Output: 1

Constraints

• 1 ≤ n ≤ 30,000

Intuition

A brute-force method would involve checking every number from 1 to n, squaring it, and comparing with n. But this results in O(n) time complexity.

Given the nature of the problem (searching for a number in a monotonic increasing function — i.e., x * x), we can use Binary Search to optimize the solution to O(log n).

Approach

1. Initialize a search range from start = 1 to end = n.

2. Apply binary search:

   • Compute mid = start + (end - start) / 2

   • Compute mid * mid:

     • If it's equal to n, return mid

     • If it's greater than n, move to the left half (end = mid - 1)

     • If it's less than n, move to the right half (start = mid + 1)

3. If no perfect square is found, the floor of the square root is end (the last number for which mid * mid <= n).

Java Code

class Solution {
    int floorSqrt(int n) {
        int start = 1;
        int end = n;

        while (start <= end) {
            int mid = start + (end - start) / 2;
            int currSqr = mid * mid;

            if (currSqr == n) {
                return mid;
            } else if (currSqr > n) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return end; // floor value
    }
}

Time and Space Complexity

• Time Complexity: O(log n)
  Binary search halves the search space at each step.

• Space Complexity: O(1)
  Constant space is used regardless of input size.

Dry Run

Input:

n = 11

Binary Search Steps:

• start = 1, end = 11
mid = 6, 6^2 = 36 > 11 → end = 5

• start = 1, end = 5
mid = 3, 3^2 = 9 < 11 → start = 4

• start = 4, end = 5
mid = 4, 4^2 = 16 > 11 → end = 3

Now start = 4, end = 3 → loop terminates

Return end = 3, which is the floor of √11

Conclusion

This is a classic binary search problem over a monotonic mathematical function (x * x). It serves as a foundational example for applying binary search to solve numeric approximation problems efficiently.

Using Binary Search ensures a logarithmic time solution with no additional space, making it both optimal and scalable for higher input ranges.