Valid Perfect Square | LeetCode

Companies:
  • Adobe Interview Questions
  • Apple Interview Questions
  • Flipkart Interview Questions
  • Oracle Interview Questions

Given a number N, check if it is a valid perfect square or not.

A valid perfect square is a number which can be written as product of two integers.
Input: 16
Output: true 
Explanation: This is true because 16 can be written as square of 4
Input: 14
Output: false
Explanation: 14 is not a perfect square.

Solution

The naive way would be to just iterate over all the integers from 1 to N and check if N is perfect square of one of the integers. However, in the worst case this would lead to a time complexity of O(N)

We can optimize the above solution further, if we observe one important property of any integer.

For any integer X if X*X > N, then the square root of N lies to the left of X and vice-versa.

We can use the above observation to optimize our solution by using binary search.

Initially, low would be 1 and high would be N. At each step will compute the mid point of low and high and then check if its square is greater than or less than N. If it is greater than N, then we search in the left half , if it is less than N, we search in the right half, as shown in the diagram below

See the below code for implementation

Solution Implementation

class Solution {
public:
    bool isPerfectSquare(int num) {
        unsigned long long int low = 1;
        unsigned long long int high = num;
        while (low <= high) {
          unsigned long long int mid = (low + high)/2;
          unsigned long long int sq = mid*mid;
          if (sq < num) {
            low = mid + 1;
          }
          else if (sq > num) {
            high = mid - 1;
          }
          else {
            return true;
          }
        }
      return false;
    }
};
Scroll to Top