# Determine if given number is a perfect square? Can't use Math.Sqrt library function

• 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

• Is 0 a perfect square?

• @1337c0d3r nope... starts from 1

• 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;
}
``````

• The Newton Iteration Method runs a little faster. Suppose the initialized square root is x0, use x1 = -f(x0) / f'(x0) + x0 and x0 = x1 to update, until satisfy the precision. Forgive me use the picture here...

• @fujiaozhu I cannot see the picture

• @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.

• @1337c0d3r ,@fujiaozhu thank you

• @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?

• @elmirap Yes, that's what the code did.

• @fujiaozhu Great approach.

• 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)

• Here is my simple C# solution :

public class Solution {
public bool IsPerfectSquare(int n) {

``````	for(int i=1; i*i<=n; i++)
{
if(i*i == n)
return true;
}
return false;
}
``````

}

• 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 :)

• Simple O(√n) Python solution

``````def is_square(n):
x=1
while x*x <= n:
if x*x == n: return True
x+=1
return False
``````

What do you think?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.