2
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ when running this program, the user is left with a blinking cursor and no indication of what to input. TO avoid that problem, always prompt the user for each input \$\endgroup\$ – user3629249 Jul 28 '15 at 13:57
  • \$\begingroup\$ the 'sqrt()' function is found in math.h, so the code is missing '#include <math.h>' \$\endgroup\$ – user3629249 Jul 28 '15 at 13:58
  • \$\begingroup\$ when using scanf(), always check the returned value (not the parameter value) to assure the operation was successful. \$\endgroup\$ – user3629249 Jul 28 '15 at 14:00
  • 1
    \$\begingroup\$ tutorialspoint.com/c_standard_library/c_function_scanf.htm \$\endgroup\$ – jacwah Jul 28 '15 at 14:04
  • 2
    \$\begingroup\$ If the problem is taken from some online resource (i.e. some code competition) I think you should link to it. \$\endgroup\$ – Emanuele Paolini Jul 28 '15 at 15:40
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ A good realistic solution for very nice speeds... but not exactly a demonstration of automation and/or calculation on demand. \$\endgroup\$ – insidesin Jul 28 '15 at 16:18
  • \$\begingroup\$ Of course it is very simple to make the computation on demand in case the upper bound was not given. However the complexity becomes O((max b)^(1/2)) while this solution has complexity O(1). \$\endgroup\$ – Emanuele Paolini Jul 28 '15 at 16:23
  • \$\begingroup\$ Except it's not a solution. It's a work-around. That's like saying the solution to being fit is to not eat. \$\endgroup\$ – insidesin Jul 28 '15 at 17:05
0
\$\begingroup\$

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 ¯\_(ツ)_/¯

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ you can make this more accurate by checking if the 'square of the square root' of the 'low' number is the 'low' number \$\endgroup\$ – user3629249 Jul 28 '15 at 15:40
  • 2
    \$\begingroup\$ This is plain wrong. Please read the exercise again. Your definition of perfect square is not the same as in the exercise and thus your program will give the wrong results. You did not even bother to run the provided samples, otherwise you would have noticed. Also, prompting should not be done, otherwise OP won't be able to submit the task to an online-judge. Sorry to say so, but better not having a review than this one... \$\endgroup\$ – dingalapadum Jul 28 '15 at 15:48
  • \$\begingroup\$ you can easily add a second step to see if the found 'perfect square' values are them selves perfect squares. Per the problem definition, only need to look one level deep \$\endgroup\$ – user3629249 Jul 28 '15 at 15:51
  • \$\begingroup\$ @dingalapadum, nothing was stated in the problem about needing to submit to a on-line judge. and I did run the sample inputs (and a lot of others). I have commented on the need to add a second level of checking. I did include a caveat about certain inputs (none of the provided samples shows the problem) would be off by one. The question was about how to speed up the algorithm. The algorithm I provided is very fast and adding a recursive feature to check if the inputs are themselves perfect squares is easy. I provided direction, I did not provide the OPs homework for them \$\endgroup\$ – user3629249 Jul 28 '15 at 15:58
  • \$\begingroup\$ well. it also doesn't say you should prompt your user, does it? Also, enter the range 100 10000. It says that the output should be 9. What does your program give you? \$\endgroup\$ – dingalapadum Jul 28 '15 at 16:05
0
\$\begingroup\$

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.

\$\endgroup\$

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.