4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – user3629249 Jan 25 '15 at 8:23
  • \$\begingroup\$ this line: 'scanf("%d %d",&a,&b);' is inputting to UNSIGNED variables. %d is for signed int. suggest 'scanf("%u %u",&a,&b);' \$\endgroup\$ – user3629249 Jan 25 '15 at 8:27
  • \$\begingroup\$ the code does not produce a forever loop; So what is timing out? \$\endgroup\$ – user3629249 Jan 25 '15 at 8:33
  • \$\begingroup\$ 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. \$\endgroup\$ – thebenman Jan 25 '15 at 16:26
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ That was a really smart solution. Thanks :) \$\endgroup\$ – thebenman Jan 25 '15 at 6:33
  • \$\begingroup\$ @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. \$\endgroup\$ – JPMC Jan 25 '15 at 6:55
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – JPMC Jan 25 '15 at 16:41
  • \$\begingroup\$ @janos Thanks a lot :) Will try and follow them from now on. \$\endgroup\$ – thebenman Jan 25 '15 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.