---
Difficulty: Easy
Source: 160 Days of Problem Solving (BONUS PROBLEMS π)
Tags:
- Searching
- Mathematical
- Binary Search
---
# π _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
