0300 - 0399
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: trueExample 2:
Input: num = 14
Output: falseConstraints:
1 <= num <= 2^31 - 1
Approach 1: Binary Search
:::info Prerequisite
:::
This approach is similar to Standard Binary Search, just need check for and . 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 time complexity and 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;
}
};class Solution {
public boolean isPerfectSquare(int num) {
// Binary Search
// choosing long because of overflow
long s = 0, e = num;
while (s <= e) {
long mid = s + (e - s) / 2;
// check if it's a perfect square
if (mid * mid == num) {
return true;
}
// checks where num lies above or below mid*mid
// then change the values of s or e accordingly
if (mid * mid < num) s = mid + 1;
else e = mid - 1;
}
// return false if no result found
return false;
}
}class Solution:
def isPerfectSquare(self, num: int) -> bool:
left = 0
right = num
while left <= right:
mid = (left + right) // 2
if mid ** 2 == num:
return True
elif mid ** 2 < num:
left = mid + 1
else:
right = mid - 1
return False/**
* @param {number} num
* @return {boolean}
*/
var isPerfectSquare = function (num) {
let left = 0;
let right = num;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (mid ** 2 === num) {
return true;
} else if (mid ** 2 > num) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return false;
};