367. Valid Perfect Square

1. Description

Given a positive integer num, return true if num is a perfect square or false otherwise.
A perfect square is an integer that is the square of an integer. In other words, it is the product of some integer with itself.
You must not use any built-in library function, such as sqrt.

2. Example

Example 1

Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.

Example 2

Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.

3. Constraints

• 1 <= num <= 2$^{31}$ - 1

4. Solutions

Binary Search

n = num
Time complexity: O(logn)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool isPerfectSquare(int num) {
        // since the range of num is [1, 2^31 - 1], we must consider overflow
        // the simplest method is using long rather than int
        for (long left = 1, right = num; left <= right;) {
            long mid = left + (right - left) / 2;

            if (mid * mid == num) {
                return true;
            }

            mid * mid < num ? left = mid + 1 : right = mid - 1;
        }

        return false;
    }
};