4. Square Root.md

Difficulty	Source	Tags
Easy	160 Days of Problem Solving (BONUS PROBLEMS 🎁)	Searching Mathematical Binary Search

🚀 4. Square Root 🧠

The problem can be found at the following link: Problem Link

💡 Problem Description

Given a positive integer n, find the square root of n. If n is not a perfect square, return the floor value.

The floor value of any number is the greatest integer which is less than or equal to that number.

🔍 Example Walkthrough

Input:

n = 4

Output:

2

Explanation:
Since 4 is a perfect square, its square root is 2.

Input:

n = 11

Output:

3

Explanation:
Since 11 is not a perfect square, the floor of the square root of 11 is 3.

Input:

n = 1

Output:

1

Explanation:
Since 1 is a perfect square, the square root is 1.

Constraints:

• $1 ≤ n ≤ 3 \times 10^4$

🎯 My Approach

1. Binary Search Initialization:
   We initialize two pointers lo (low) and hi (high), where lo = 0 and hi = n.

2. Binary Search Loop:
   We perform a binary search to find the integer square root of n. The middle element mid is computed as:

   mid = lo + (hi - lo) / 2
   

3. Check for Square:
   If mid * mid <= n, we update the result to mid (since it is a valid candidate for the square root) and shift the lo pointer to mid + 1. Otherwise, we move the hi pointer to mid - 1.

4. End Condition:
   The loop continues until lo exceeds hi, and at the end of the search, the value stored in ans will be the largest integer whose square is less than or equal to n.

🕒 Time and Auxiliary Space Complexity

• Time Complexity: O(log n), where n is the number for which we are finding the square root. In each iteration of the binary search, we are halving the search space.
• Auxiliary Space Complexity: O(1), as we only use a few integer variables for the binary search and result tracking.

📝 Solution Code

Code (C)

int floorSqrt(int n) {
    int lo = 0, hi = n, ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if ((long long)mid * mid <= n) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

Code (C++)

class Solution {
  public:
    int floorSqrt(int n) {
        int lo = 0, hi = n, ans = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if ((long long)mid * mid <= n) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }
};

Code (Java)

class Solution {
    int floorSqrt(int n) {
        int lo = 0, hi = n, ans = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if ((long)mid * mid <= n) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return ans;
    }
}

Code (Python)

class Solution:
    def floorSqrt(self, n):
        lo, hi = 0, n
        ans = 0
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if mid * mid <= n:
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

📢 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count