Write a function that takes an integer as input and returns true if it's a perfect square else false.
public static bool IsPerfectSquare(int n)
{
}
ex: Perfect squares = 16 (4x4), 25 (5x5) etc
here is my python code
def IsPerfectSquare(num):
if num <= 0:
return False
if num == 1:
return True
start = 1
while start * start * 4 <= num:
start *= 2
end = start * 2
while start + 1 != end:
mid = (start + end ) / 2
if mid * mid == num:
return True
elif mid * mid > num:
end = mid
else:
start = mid
return False
Binary search.
public boolean IsPerfectSquare(long n)
{
if (n <= 0)
return false;
if (n == 1)
return true;
long l = 1;
long r = n;
while (l <= r) {
long mid = l + (r - l )/2;
long square = mid * mid;
if (square == n) {
return true;
} else if (square > n) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
@elmirap I just edited @fujiaozhu post and I can see the picture. Try reloading the page?
@1337c0d3r still cannot see it. I can read the message [0_1465713406824_MP_EB9P6FMYM245JI5]HVRS.png](/uploads/files/1465713250393-mp_eb9p6fmym245ji5-hvrs.png)
@elmirap Actually I don't know how to add the code..the code in the picture is:
bool IsPerfectSquare(int n) {
if (n <= 0)
return false;
double x0 = n, x1;
const double eps = 1e-3;
while(true) {
x1 = -(x0 * x0 - n) / (2 * x0) + x0;
if(abs(x1 * x1 - n) <= eps)
break;
x0 = x1;
}
return (int)x1 * (int)x1 == n;
}
@elmirap Ya that's what I saw before too. That's probably due to caching issue in the forum. Eventually it will resolve itself, but one way to get around it is to click on the "quote" button in the post, then you can see the picture appearing in your edit post textarea.
@fujiaozhu , is it true, that you try to find the root of function x^2 - n= 0 with some error of 1e-3 and than check if root is prefect square?
here is my python code:
def Issquare(num):
y = 0
if num >= 0:
while y * y < num:
y = y + 1
if y * y !=num:
print(num, "is a not a perfect sq")
return None
else:
print(num, "is a perfect sq of : ", y)
return num
else:
print(num,"is not a postive number")
return None
Issquare(4)
JavaScript solution(s):
function isSquare(num) {
if (num < 1)
return false;
for (var idx = 1; idx*idx <= num; idx++) {
if (idx*idx === num)
return true;
}
return false;
}
Recursive version:
function isSquare(num) {
if (num < 1)
return false;
function find(idx) {
if (idx*idx > num)
return false;
else if (idx*idx === num)
return true;
else
return find(idx + 1);
}
return find(1);
}
Just because, the boring iterative number-theory solution, implemented for Python (2 or 3):
import itertools
try:
filter = itertools.ifilter
except AttributeError:
pass
def is_square(n):
if n == 0: # If you consider 0 to be a perfect square.
return True
seq = filter(lambda i: i % 2, itertools.count())
sum = 0
while sum < n:
sum += next(seq)
if sum == n:
return True
return False
Works because the square of an integer n
is equal to the sum of the first n
odd integers, a fact that is rarely useful to know.
Not the fastest thing, but fortunately the really noticeable slowness due to iteration kicks in past the range of Java's int
type :)