### Problem Statement

Given a positive integer *num*, write a function which returns True if *num* is a perfect square else False.

**Note:** **Do not** use any built-in library function such as `sqrt`

.

**Example 1:**

```
Input: 16
Output: true
```

**Example 2:**

```
Input: 14
Output: false
```

### Solution

```
class Solution {
public:
bool isPerfectSquare(int num) {
int L = 0, U = num;
bool result = false;
while(L<=U)
{
long long mid = L + (U-L)/2;
long long squaredValue = mid * mid;
if(squaredValue > num)
{
U = mid-1;
}
else if(squaredValue < num)
{
L = mid+1;
}
else
{
result = true;
break;
}
}
return result;
}
};
```

### Solution Thought Process

We can solve the problem using linear time, where we are checking every value and it's square starting from 1. We will terminate the loop when we have found a square which is equal to the number. If we haven't found and the squared value is greater than the number, then we return false.

But we can do better here using binary search. We set the `L = 0`

and `U = num`

. We set the mid according to binary search rules. Then we calculate it's square value, if the square value is greater than num, it means that any number less than mid can have a chance for being the square root. So we adjust the upper limit to `mid-1`

.

If we see that the squared value is less than num, then we can say that any number greater than mid can have a chance for being the square root. So we adjust the lower limit to `mid+1`

.

If the squared value is equal to `num`

, we return true and break the binary search.

Look out for integer overflow, we can solve it by setting `mid`

and `squaredValue`

into `long long int`

.

### Complexity

**Time Complexity:** O(logn), we are just iterating over the points.

**Space Complexity:** O(1).

## Top comments (0)