Find perfect squares between two numbers

Question

The following problem is from codechef.com:

Recently Chef become very much interested in perfect squares. We all know Chef and his weird interests. Anyways Chef will be soon writing his masters thesis on perfect squares revealing what-not-known properties of perfect squares. While doing his research, he happened to be confronted with some interesting perfect squares. These prefect squares consists only of digits which are themselves perfect squares. 0, 1, 4 and 9 are such digits. These are called perfect digits.

As we all know Chef also has habit of asking too many questions, he is asking- given two numbers a and b, how many perfect squares exists between these two numbers inclusive, that contains only perfect digits.

Input:

First line of input will contains T, number of test cases. Then T lines follows, each containing two positive integers a and b.

Constraints:

• \$T \le 500\$
• \$1 \le a \le b \le 10000000000\$

Output:

For each input, output number of perfect digit squares between given numbers.

Sample:

Input:

2
1 10
100 10000
 Output:

3
9

How can I decrease the running time of my solution?

#include<stdio.h>
int main()
{
    int test;
    long long int num1,num2,start,stop,i,j,square,rem;
    scanf("%d",&test);
    while(test--)
    {
        long long int count=0;
        scanf("%lld%lld",&num1,&num2);
        start=sqrt(num1);
        stop=sqrt(num2);
        for(i=start;i<=stop;i++)
        {
            square = i*i;

            if(square<num1)
            {
                continue;
            }
            else
            {
                while(1)
                {

                    rem=square%10;
                    if(rem!=1 && rem!= 4 && rem!=9 && rem!=0 )
                    {
                        break;
                    }
                    if(square>=10)
                    {
                        square=square/10;

                    }
                    else
                    {
                        if(square!=1 && square!= 4 && square!=9 &&square!=0 )
                        {
                                break;
                        }
                        else
                        {
                            count+=1;
                        }
                        break;
                    }
                }
            }
        }
        printf("%lld\n",count);
    }
    return 0;
}

Answer 1

I didn't have a very close look at your solution, but a simple (algorithm-agnostic way) to improve efficiency for this kind of task, is to cache (think about which data structure would suit this task) previously found solutions. For instance consider test 1 being a=1, b=10000 and test 2 exactly (or almost) the same, like for instance a=1 and b=10000 or a=2 and b=9999. You are going to check recompute the whole thing, although you just did that.

p.s.: I'll have a closer look at it if you are still struggling with it when I get home.

Answer 2

You should notice that square numbers between 1 and 1000000000 are "only" 100000 and among them you can imagine that very very few can possibly have all perfect digits since the condition on every single digits are probably independent and hence you expect 1 every 2^10 perfect squares with perfect digits. So you could compute them all at once and, possibly, put them in your code (you find they are only 121 numbers). Finally you can find how many of them are in a given interval with a simple linear search.

On my laptop, with the worst case input, your code runs in 2.871s while the following one runs in 0.017s.

#include <stdio.h>
#include <math.h>
#include <assert.h>

long long perfect_squares[100000] = {
    0, 1, 4, 9, 49, 100, 144, 400, 441, 900, 1444, 4900, 9409, 10000, 
    10404, 11449, 14400, 19044, 40000, 40401, 44100, 44944, 90000, 
    144400, 419904, 490000, 491401, 904401, 940900, 994009, 1000000, 
    1004004, 1014049, 1040400, 1100401, 1144900, 1440000, 1904400, 
    1940449, 4000000, 4004001, 4040100, 4410000, 4494400, 9000000, 
    9909904, 9941409, 11909401, 14010049, 14040009, 14440000, 19909444, 
    40411449, 41990400, 49000000, 49014001, 49140100, 49999041, 90440100, 
    94090000, 94109401, 99400900, 99940009, 100000000, 100040004, 
    100140049, 100400400, 101404900, 101949409, 104040000, 104919049, 
    110040100, 111049444, 114041041, 114490000, 144000000, 190440000, 
    194044900, 400000000, 400040001, 400400100, 404010000, 404090404, 
    409941009, 414000409, 414041104, 441000000, 449440000, 490091044, 
    900000000, 990990400, 991494144, 994140900, 1190940100, 1401004900, 
    1404000900, 1409101444, 1444000000, 1449401041, 1490114404, 
    1990944400, 4014109449, 4019940409, 4041144900, 4199040000, 
    4900000000, 4900140001, 4901400100, 4914010000, 4914991449, 
    4941949401, 4999904100, 9044010000, 9409000000, 9409194001, 
    9410940100, 9900449001, 9940090000, 9994000900, 9999400009, 
    10000000000};
int count = 121;

int has_perfect_digits(long long n) {
  while(n>0) {
    int d = n % 10;
    if (!(d==0 || d==1 || d==4 || d==9)) return 0;
    n /= 10;
  }
  return 1;
}

void compute_perfect_squares() {
  long long i;
  for (i=0;;++i) {
    long long s = i*i;
    if (s>10000000000) break;
    if (has_perfect_digits(s))
      perfect_squares[count++] = s;
  }
}

int count_perfects(long long a, long long b) {
  int c=0;
  int i;
  for (i=0;;++i) {
    assert(i<count);
    if (perfect_squares[i] > b) break;
    if (perfect_squares[i] >= a) c++;
  }
  return c;
}

int main()
{
  int test;
  long long int a, b;

  if (0) { // enable this to get the values of perfect_squares
    int i;
    compute_perfect_squares();
    printf("%d\n", count);
    for (i=0;i<count;++i) {
      printf("%lld, ", perfect_squares[i]);
    }
    return 0;
  }

  scanf("%d",&test);
  while(test--)
    {
      long long int count=0;
      scanf("%lld%lld", &a, &b);
      printf("%d\n", count_perfects(a, b));
    }
}

note: in C++ it would be easy to make the computation of the array of the perfect squares at compile time. Maybe also in C it could be possible (using #defines) but not as easily.

Answer 3

This code is a bit inefficient:

for (i=start;i<=stop;i++) {
  square = i*i;

A much faster way of iterating through successive square numbers is to use addition instead of multiplication. Like this, for example:

scanf("%lld %lld",&num1,&num2);
sq = (long long)sqrt((double)num1);
sqdelta = 2*sq + 1
sq = sq * sq;

/* Increase sq to first square >= num1 */
while (sq < num1) {
  sq += sqdelta;
  sqdelta += 2;
}

/* Test all squares from num1 to num 2 inclusive */
count = 0;
while (sq <= num2) {

  /* Does this square consist of digits 0, 1, 4 and 9 only? */
  tmp = sq;
  while (tmp) {
    last_digit = tmp % 10;
    if (last_digit>1 && last_digit!=4 && last_digit!=9) break;
    tmp /= 10;
  }

  /* If so, increment counter */
  if (!tmp) count++;

  /* Calculate next square number */
  sq += sqdelta;
  sqdelta += 2;
}

---

_{Note: although this code only takes about 1 second to run 500 tests with a=1 and b=10000000000 on my 5-year-old computer, it still times out at CodeChef. So perhaps you would be better off using @Emanuale's solution ¯\_(ツ)_/¯}

Answer 4

The following code compiles cleanly. Caveat: this code may be off by 1 with certain input values.

I added several 'debug' statements to make execution easier to follow. Notice the following code checks for errors. I removed the loop that allowed for multiple sets, you can easily add that to the code. I added prompts for each input the user is to make. I did not check to assure the second user input number is > the first user input number. You can easily add that to the code.

The definition of a perfect square is:

A perfect square is a number that has an whole number square root

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main( void )
{
    long long int num1,num2;  // user inputs
    long long int start,stop; // calculated limits
    long long int count=0;    // calculated output

    printf( " Enter low end of range of numbers to check for perfect squares:");
    if( 1 != scanf("%lld", &num1) )
    { // then scanf failed
        perror( "scanf for num1 failed");
        exit( EXIT_FAILURE );
    }

    // implied else, scanf for num1 successful

    printf( " Enter high end of range of numbers to check for perfect squares:");
    if( 1 != scanf("%lld", &num2) )
    { // then scanf failed
        perror( "scanf for num2 failed");
        exit( EXIT_FAILURE );
    }


    start=sqrt(num1);                            printf("low sqrt: %lld\n", start);
    stop=sqrt(num2);                             printf("high sqrt: %lld\n", stop);

    count = stop - start +1;
    printf("%lld\n", count);

    return 0;
}

Answer 5

Don't repeat yourself (DRY)

                    rem=square%10;
                    if(rem!=1 && rem!= 4 && rem!=9 && rem!=0 )
                    {
                        break;
                    }
                    if(square>=10)
                    {
                        square=square/10;

                    }
                    else
                    {
                        if(square!=1 && square!= 4 && square!=9 &&square!=0 )
                        {
                                break;
                        }
                        else
                        {
                            count+=1;
                        }
                        break;
                    }

This is more complicated than necessary. You check the last digit twice here (once as rem and once as square; note that they are equal if square is less than ten). You could just say

                    rem = square%10;
                    if (rem!=1 && rem!= 4 && rem!=9 && rem!=0 )
                    {
                        break;
                    }

                    if (square < 10)
                    {
                        count++;
                        break;
                    }

                    square = square / 10;

Basically this says that if the rightmost digit is not a square, break. If less than ten, then we've checked all the digits, so increment the count and break. Divide by ten if we make it that far.

The count++ is more idiomatic C than count += 1.

I would prefer to see rem written out as either remainder or digit. The latter is more descriptive in my opinion.

Possible optimization

You can also save some code (and possibly time) by using an array to hold Boolean values for each digit.

int imperfect[10] = { 0, 0, 1, 1, 0, 1, 1, 1, 1, 0 };

Then you could replace

                    rem=square%10;
                    if(rem!=1 && rem!= 4 && rem!=9 && rem!=0 )
                    {
                        break;
                    }

with

                    if (imperfect[square % 10])
                    {
                        break;
                    }

If it can do the pointer math faster than four comparisons and three logical operators, this could be faster. You'd have to benchmark to be sure.