4
\$\begingroup\$

Below is the code I have written for counting perfect squares between a given lower and upper bound.

I am using the following concept to solve this:

Starting with 1, there are \$\sqrt{m}\$ square numbers up to and including \$m\$.

public static int CountPerfectSquares(long A, long B)
{            
    int count = 0;

    //Proceed if lowerbound is less than upperbound
    if (A < B)
    {
        //negative numbers are not perfect squares
        if (A < 0 && B < 0) return count; 

        //Reset lowerbound if required
        if (A <= 0) A = 1;

        //Find number of squares between A & B (INCLUSIVE lower and upperbound)
        //count = (int)Math.Sqrt(B) - (int)Math.Sqrt(A);  //Giving wrong count when LowerBound value is a whole square (For exp. CountPerfectSquares(1, 25))

        int sqrtA = (int)Math.Sqrt(A);
        int sqrtB = (int)Math.Sqrt(B);
        count = sqrtB - sqrtA;
        //To handle the case when lowerbound value is a perfect square number
        if (A == sqrtA * sqrtA) 
        {
            count++;
        }
    }

    return count;
}

Can you please help me make this more efficient, if possible?

Is there any other way of handling the case when the lower bound value is a perfect square number, so that I don't have to do an extra count++?

\$\endgroup\$
  • \$\begingroup\$ you are over thinking this one. \$\endgroup\$ – Malachi Oct 16 '13 at 17:00
  • \$\begingroup\$ you can just return the Square root of the larger Number as the count, if you don't give the application perfect squares then that is a different issue \$\endgroup\$ – Malachi Oct 16 '13 at 17:02
6
\$\begingroup\$

If A was not included in the observed range, you wouldn't need the if (A == sqrtA * sqrtA) part, right? So, let's use that: instead of checking the range {A,A+1,...,B}, check the range {A-1,A,...,B}. Since you're working with integers, the two are the same:

        int sqrtA = (int)Math.Sqrt(A-1);
        int sqrtB = (int)Math.Sqrt(B);
        count = sqrtB - sqrtA;

A minor detail: when returning a predefined constant, I prefer writing the constant itself, not a variable initialized to that value:

        if (A < 0 && B < 0) return 0; 

It seems more readable to me.

Also, I would replace two main if-s with if (B < 0 || B < A) return 0. This gives the same result, but in a cleaner way.

So, my version would be:

public static int CountPerfectSquares(long A, long B)
{            
    // Return zero if there are obviously no perfect squares
    if (B < 0 || B < A) return 0;

    // Reset the lower bound if required
    if (A <= 0) A = 1;

    // Find the number of perfect squares between A & B (INCLUSIVE)
    return (int)Math.Sqrt(B) - (int)Math.Sqrt(A-1);  // Now giving the correct count, even when the lower bound value is a whole square (for exp. CountPerfectSquares(1, 25))
}
\$\endgroup\$
  • \$\begingroup\$ +1. You could refactor this even further: public static int CountPerfectSquares(long A, long B) { if (A <= 0) A = 1; return B < 0 || B < A ? 0 : (int)Math.Sqrt(B) - (int)Math.Sqrt(A-1); } \$\endgroup\$ – JᴀʏMᴇᴇ Oct 16 '13 at 12:11
  • \$\begingroup\$ @DeeMac This would reduce readability, with no benefits (at least obvious to me). Btw, you could replace B < 0 || B < A with B < A, since you've already changed A. ;-) \$\endgroup\$ – Vedran Šego Oct 16 '13 at 12:14
  • \$\begingroup\$ Nice! Fair point about the readability. \$\endgroup\$ – JᴀʏMᴇᴇ Oct 16 '13 at 12:15
  • \$\begingroup\$ really if you are being inclusive as you are, you can just return the Square root of the larger Number as the count. if you are going to give the application perfect squares and you are not going into imaginary numbers and you count 1. \$\endgroup\$ – Malachi Oct 16 '13 at 16:57
  • \$\begingroup\$ @Vedran, Thanks a lot for the review and also for pointing out returning constant value. It does improve readability :-) \$\endgroup\$ – iniki Oct 16 '13 at 20:46

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.