# Efficient way of finding perfect squares

I was trying to solve a problem which needed you to count the number of perfect squares in the given range:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int isPerfectSquare(int x)
{
float s = sqrt(x);
if (fmod(s,1) ==0)
return 1;
else
return 0;
}
int main() {

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int testcases;
unsigned int a,b;
scanf("%d",&testcases);
while(testcases--)
{
int counter =0;
scanf("%d %d",&a,&b);
unsigned int i;
for(i=a;i<=b;i++)
{
int last_digit = i%10;
if( (last_digit == 2) || (last_digit == 3) || (last_digit == 7) || (last_digit == 8) )
continue;
else
{
if (isPerfectSquare(i))
counter++;
}
}
printf("%d\n",counter);
}
return 0;
}


However, this code fails for certain test cases due to a timeout. I found that perfect squares do not end with a 2 or 3 or 7 or 8 so I ignored such values. Yet, I'm unable to solve this problem within the required run time.

I have found similar questions here, but either they were not in C or they didn't have answers that were quite relevant to C.

Could you suggest a way that I can optimize this code so that it could run faster?

• 1) the returned value from I/O functions (I.E. scanf) should be check to assure the input/ conversion operation was successful. 2) the format string for scanf() should contain a leading ' ' (space) so any left over white space in stdin is consumed/skipped over. – user3629249 Jan 25 '15 at 8:23
• this line: 'scanf("%d %d",&a,&b);' is inputting to UNSIGNED variables. %d is for signed int. suggest 'scanf("%u %u",&a,&b);' – user3629249 Jan 25 '15 at 8:27
• the code does not produce a forever loop; So what is timing out? – user3629249 Jan 25 '15 at 8:33
• Thanks for the suggestions. The code needs to run within a time limit, which this particular code couldn't and hence it causes a timeout. – thebenman Jan 25 '15 at 16:26

You could easily find the number of perfect squares up to (and including) a number by simply using (int)sqrt(x)

If you want the number of squares between two numbers, you should simply need to do this:

(int)sqrt(max) - (int)sqrt(min)


Though note if min is a perfect square, it is excluded/subtracted from the range. You can use a +/- 1 if you want to exclude the max number (if it's a perfect square), or include the min number (if it's a perfect square), from the range.

• That was a really smart solution. Thanks :) – thebenman Jan 25 '15 at 6:33
• @user3575018 Glad I could help! :) Let me know if you need any more specific information about including/excluding parts of the range if my last sentence doesn't explain it well enough. – JPMC Jan 25 '15 at 6:55

In addition to the main problem pointed out by @JPMC's excellent review, there are some coding style issues too that deserve mentioning and you should improve for the future.

    if (fmod(s,1) ==0)
return 1;
else
return 0;


This is good to shorten using the ternary operator:

return fmod(s,1) == 0 ? 1 : 0;


And since the == operator returns 1 for true and 0 for false, this can be further simplified to:

return fmod(s, 1) == 0;


The placement of opening braces and the indentation is strange in some places, for example:

    while(testcases--)
{
int counter =0;
// ...
for(i=a;i<=b;i++)
{
int last_digit = i%10;
if( (last_digit == 2) || (last_digit == 3) || (last_digit == 7) || (last_digit == 8) )
continue;


Since in other places you put the opening brace on the same line as the statement (also known as Egyptian style), you should follow that style consistently everywhere:

    while(testcases--) {
int counter =0;
// ...
for(i=a;i<=b;i++) {
int last_digit = i%10;
if( (last_digit == 2) || (last_digit == 3) || (last_digit == 7) || (last_digit == 8) )
continue;


I recommend to put spaces around operators, and after ;, like this:

        for (i = a; i <= b; i++) {


Also after commas in function parameter lists:

        scanf("%d %d", &a, &b);


The parentheses around the equality tests are redundant here:

            if( (last_digit == 2) || (last_digit == 3) || (last_digit == 7) || (last_digit == 8) )


You could write simpler as

            if (last_digit == 2 || last_digit == 3 || last_digit == 7 || last_digit == 8)


Finally, I recommend to use braces with even single-statement ifs, otherwise embarrassing bugs might happen one day.

• I would like to point out those are great coding tips (spacing, boolean reduction, etc), though I would like to point out that you need to be careful where you use ternary operators. Skipping the if/else is great in the end, but that ternary bit beforehand is sometimes a grey area. Most people say it hinders readability for people. I personally like them and use them for quick statements like that, but have read a few S.E. answers that discourage it, as well as at my workplace. Not a huge deal, but mostly people worrying about the readability of code. So use ternary statements wisely! – JPMC Jan 25 '15 at 16:41
• @janos Thanks a lot :) Will try and follow them from now on. – thebenman Jan 25 '15 at 17:03