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.
Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.
Input: num = 14
Output: false
Explanation: We return false because 3.742 * 3.742 = 14 and 3.742 is not an integer.
Constraints:
- 1 <= nums.length <= 231-1
Contents
- Solution 1 - Using binary search
In the problem statement, it is mentioned that we cannot use any inbuilt functions such as Math.sqrt(num).
So one possible solution we could implement is, check square of each number starting from 1 and check whether it matches
input num, if it matches we can return true, otherwise continue until we find the square of a number that matched input number
and when we go beyond input number and cant find a perfect square then return false, and the time complexity of this approach is going to be O(√n).
We can solve this problem using binary search, which runs in O(log n) time complexity. So, in this approach,
we will initialize two variables left =1 and right = num that acts as left and right boundaries.
Then using a while loop, compute the middle index
mid =
, then compute the square of the mid value, based on square value we can draw three conclusions.
-
If square value is equal to num, then return true since the square computed using mid is a perfect integer.
-
If square value is greater than num, this means that the target lies on left side,
so we will update right value to mid-1.
-
If square value is less than num, this means that the target lies on right side,
so we will update left value to mid+1.
If that num is not found, we will return false at the end.
public class ValidPerfectSquare {
static boolean isPerfectSquare(int num) {
int left = 1;
int right = num;
while(left <= right) {
int mid = left + (right - left) /2;
long sqrt = (long)mid * mid;
if (sqrt == num) {
return true;
} else if (sqrt > num) {
right = mid-1;
} else {
left = mid+1;
}
}
return false;
}
public static void main(String[] args) {
System.out.println(isPerfectSquare(16));
System.out.println(isPerfectSquare(14));
System.out.println(isPerfectSquare(2147483647));
}
}
Complexity Analysis:
Time complexity: Above code runs in O(log n) time where n is the length of input number num.
Space complexity: O(1).
Above implementations source code can be found at
GitHub link for Java code