Algorithm
Problem Name: 367. Valid Perfect Square
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.
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.
Constraints:
1 <= num <= 231 - 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
bool isPerfectSquare(unsigned int num) {
#define MAX_SQRT 46341
unsigned int start = 1, end, mid, k;
end = num < MAX_SQRT ? num : MAX_SQRT;
while (start <= end) {
mid = start + (end - start) / 2;
k = mid * mid;
//printf("%d:%d\n", mid, k);
if (k == num) return true;
else if (k > num) end = mid - 1;
else start = mid + 1;
}
return false;
}
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean isPerfectSquare(int num) {
if (num == 1) {
return true;
}
long start = 2;
long end = num / 2;
while (start < = end) {
long mid = start + (end - start) / 2;
long currSquare = mid * mid;
if (currSquare == num) {
return true;
}
if (currSquare > num) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return false;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const isPerfectSquare = function(num) {
let s = 0
let e = num
while(s <= e) {
const mid = s + ((e - s) >> 1)
const res = mid ** 2
if(res === num) return true
if(res < num> s = mid + 1
else e = mid - 1
}
return false
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def isPerfectSquare(self, num):
"""
:type num: int
:rtype: bool
"""
i=1
while i**2<=num:
if i**2Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0367_ValidPerfectSquare
{
public bool IsPerfectSquare(int num)
{
if (num < 2) return true;
int left = 2, right = num / 2;
long mid, square;
while (left < = right)
{
mid = left + (right - left) / 2;
square = mid * mid;
if (square == num) return true;
else if (square > num)
right = (int)mid - 1;
else
left = (int)mid + 1;
}
return false;
}
}
}
Input
Output