0367 - Valid Perfect Square (Easy)

Problem Link

https://leetcode.com/problems/valid-perfect-square/

Problem Statement

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

Follow up: Do not use any built-in library function such as sqrt.

Example 1:

Input: num = 16
Output: true

Example 2:

Input: num = 14
Output: false

Constraints:

• 1 <= num <= 2^31 - 1

Approach 1: Binary Search

This approach is similar to Standard Binary Search, just need check for $mid*mid$ and $num$ . Finally, we also need to check for overflow, for that its better to use long long in Cpp or long in Java. This solution gives $O( log n )$ time complexity and $O( 1 )$ space complexity.

class Solution {
public:
    bool isPerfectSquare(int num) {
        // init possible range
        // for num > 2, the range is actually [2 .. num / 2]
        long long l = 1, r = num;
        while (l < r) {
            long long m = l + (r - l) / 2;
            // exclude m
            if (num > m * m) l = m + 1;
            // include m
            else r = m;
        }
        // check if it is a perfect square
        return l * l == num;
    }
};