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


  • 0

    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


  • 0

    Is 0 a perfect square?


  • 0

    @1337c0d3r nope... starts from 1


  • 0

    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
    

  • 4

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

  • 0
    F

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

    alt text


  • 0

    @fujiaozhu I cannot see the picture


  • 0

    @elmirap I just edited @fujiaozhu post and I can see the picture. Try reloading the page?


  • 0

    @1337c0d3r still cannot see it. I can read the message [0_1465713406824_MP_EB9P6FMYM245JI5]HVRS.png](/uploads/files/1465713250393-mp_eb9p6fmym245ji5-hvrs.png)


  • 1
    F

    @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;
    }


  • 0

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


  • 0

    @1337c0d3r ,@fujiaozhu thank you


  • 0

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


  • 0
    F

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


  • 0

    @fujiaozhu Great approach.


  • 1
    A

    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)


  • 2
    *

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

    }


  • 0
    S

    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);
    }
    

  • 0
    U

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


  • 0
    G

    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?


Log in to reply
 

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