# 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;
}
``````