Implement a function to return whether an integer is perfect square


  • 0
    M

    Implement a function to return whether an integer is perfect square
    calling sub function is not accepted


  • 1
    S

    My Solution 1

    bool is_square(int x)
    {
      int i;
      for(i=0;i*i<=x;i++)
        if(i*i==x) return true;
      return false;
    }
    

    My Solution 2

    bool is_square(int x)
    {
      if(x<0) return false;
      //if(x==0) return true; //not necessary
      int i,sq;
      for(i=2;x>=(sq=i*i);i++)
      {
        if(x%sq==0)
        {
          i--;
          x/=sq;
          if(x==1) return true;
        }
      }
      return false;
    }
    

    My Solution 3

    Step 1. Find the range of root, [0, max].

    int max,max_sq;
    while((max_sq = max*max)<x)
      max = max_sq;
    

    Step 2. Binary search for the exact root. (code not carefully reviewed. may contains flaws.)

    int upper = 0;
    int lower = max;
    while(lower<upper)
    {
      int mid = (lower+upper)/2;
      if(mid*mid==x) return true;
      else if (mid*mid<x) lower = mid;
      else upper = mid;
    }
    int mid = (lower+upper)/2;
    if(mid*mid==x) return true;
    else return false;

  • 1
    Y

    Should not the answer be:

    return !(x&(x-1));

  • 0

    @yingdi11 That will only tell you if a number is a power of 2 or not. What we need to determine is if a number is a perfect square. I think using the binary search is a good solution.


  • 1
    S

    What about this -

    bool isPerfectSquare(int x){
        int p;
        p = sqrt(x);
        return (p*p==x);
    }
    

  • 1
    S

    @shubham201

    calling sub function is not accepted


  • 0
    J

    Did you get the offer?


Log in to reply
 

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