Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Optimized way to find if a number is a perfect square

I had a question in my assignment to find whether a number was perfect square or not:

Perfect square is an element of algebraic structure which is equal to the square of another element.

For example: 4, 9, 16 etc.

What my friends did is, if n is the number, they looped n - 1 times calculating n * n:

// just a general gist
int is_square = 0;
for (int i = 2; i < n; i++)
{
  if ((i * i) == n)
  {
    std::cout << "Yes , it is";
    is_square = 1;
    break;
  }
}
if (is_square == 0)
{
  std::cout << "No, it is not";
}

I came up with a solution as shown below:

 if (ceil(sqrt(n)) == floor(sqrt(n)))
 {
   std::cout << "Yes , it is";
 }
 else
 {
   std::cout << "no , it is not";
 }

And it works properly.

Can it be called as more optimized solution than others?

like image 471
Sachin Gadagi Avatar asked Feb 13 '23 03:02

Sachin Gadagi


1 Answers

The tried and true remains:

double sqrt(double x); // from lib

bool is_sqr(long n) {
    long root = sqrt(n);
    return root * root == n;
}
like image 143
Paul Evans Avatar answered Feb 20 '23 02:02

Paul Evans