# Valid Perfect Square Problem

## Description

LeetCode Problem 367. Given a positive integer **num**, write a function which returns True if **num** is a perfect square, else False. Do not use any built-in library function such as sqrt.

Example:

1
2
3
4
5

Input: num = 16
Output: true
Input: num = 14
Output: false

## Solution

This problem is similar to the `Sqrt(x) Problem`

.

#### Binary Search Approach

A simple `brute force`

approach is to enumerate all possible solutions from 1 to *num/2*, and check if there is an integer whose square equals *num*. If so, return true; otherwise, return false. The time complexity of this approach is O(n).

We can use `binary search`

to speed up the search. We set two pointers *l* and *r*. The left pointer *l* starts from 0, and the right pointer *r* starts from *num*. During each iteration, we calculate *m* to be the average of *l* and *r* (*m = (l + r) / 2*). If *m * m* equals *num*, *num* is a perfect square. We can stop the search and return true. If *m * m* is larger than *x*, it means the right range *r* is too big. We can set *r* to be *m - 1* and keep on searching. If *m * m* is smaller than *num*, it means the left range *l* is too small. We can set *l* to be *m + 1* and keep on searching. We abort the search until *l* is greater than *r*.

When *l* is greater than *r*, it means we could not find an integer whose square is *num*. Thus, *num* is not a perfect square. We return false.

The time complexity of the binary search approach is O(logn), and the space complexity is O(1).

## Sample C++ Code

This is a C++ implementation of the binary search approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <algorithm>
using namespace std;
bool isPerfectSquare(int num) {
long long l, m, r;
l = 0, r = num;
while (l <= r) {
m = (l + r) / 2;
if (m*m == num)
return true;
if (m*m < num)
l = m + 1;
else
r = m - 1;
}
return false;
}
int main() {
cout << isPerfectSquare(45) << endl;
}