Efficient way of finding perfect squares

Question

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?

• user3629249: 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: this line: 'scanf("%d %d",&a,&b);' is inputting to UNSIGNED variables. %d is for signed int. suggest 'scanf("%u %u",&a,&b);'
• user3629249: the code does not produce a forever loop; So what is timing out?
• thebenman: 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.

Answer 1

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.

• thebenman: That was a really smart solution. Thanks :)
• JPMC: @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.

Answer 2

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.

• JPMC: 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!
• thebenman: @janos Thanks a lot :) Will try and follow them from now on.