# 4. Square Root 🧠

The problem can be found at the following link: [Problem Link](https://www.geeksforgeeks.org/batch/gfg-160-problems/track/searching-bonus-problems/problem/square-root)

## 💡 **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)

```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++)

```cpp
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)

```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)

```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](https://www.linkedin.com/in/patel-hetkumar-sandipbhai-8b110525a/). Let’s make this learning journey more collaborative!

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

***

#### 📍Visitor Count

<div align="center"><img src="https://visitor-badge.laobi.icu/badge?page_id=Hunterdii.GeeksforGeeks-POTD" alt=""></div>
