 # SDSQUARE - Editorial

SIMPLE

### PREREQUISITES:

High school maths

### PROBLEM:

Calculate the number of perfect squares between a and b which do not contain any digit other than 0, 1, 4 and 9. Constraint: 1<= a <= b <= 1010

### QUICK EXPLANATION:

There are very few perfect squares satisfying the requirement, precalculating all such squares is simple.

### EXPLANATION:

The constraint on the value of b is 1010. This implies, we need to test the squares of all integers less than or equal to 10^5. Following pseudo code captures the essence of precalculating all needed squares:

``````PrecomputeSquares
{
idx = 0
for i = 1 to 10^5
{
x = i*i
if x does not contain any digit other than 0,1,4,9
squares[++idx] = x
}
}
``````

Once we have calculated these squares; for each test case, count the number of squares falling in the range specified by the test case. We can use binary search to count these squares like this:

``````lower_bound(squares.begin(), squares.end(), b+1) - lower_bound(squares.begin(), squares.end(), a);
``````

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found here and here

2 Likes

I went on to generate the numbers containing only the digits 0,1,4 and 9, and simultaneously calculated whether or not it was a perfect square. Stored it if it was. Just answered the query based on a simple lookup.

http://www.codechef.com/viewsolution/2931829

1 Like

First i pre calculated all the answers with O(sqrt(n)) complexity and then stored all the numbers in an array.Then i made a linear search and found the count. The total size of the array was only 120 elements… Why do the authors of these problems use int64 instead of long? I thought it was same… Please correct me if I’m wrong.
Is it personal opinion??

EDIT:
Okay I feel pretty stupid for asking this question. I missed the typedef long long int64.
Sorry for that. I’m new to competitive programming.

why WA

``````  /*
Ramesh Chandra 12 Sep 2015
*/
#include<bits/stdc++.h>
using namespace std;

#define write(x) printf("%lld\n",x)

int main(){

long long int t,A,B,ans,i,check;
// 1 00 00 00 00 00
int preComputedSquares;
preComputedSquares=1;

for(int i=1;i<=100000;i++){

check=i*i;
bool flag=true;

while(check && flag){

int rem=check%10;

if(rem==0 || rem==1 || rem==4 || rem==9);
else flag=false;
check/=10;
}
preComputedSquares[i]=preComputedSquares[i-1]+flag;
}

while(t--){

scanf("%lld%lld",&A,&B);
long long int L=sqrt(A-1),R=sqrt(B);
ans=preComputedSquares[R]-preComputedSquares[L];
write(ans);
}
return 0;
}``````

Actually, there are so few such numbers (just 120) that binary search is not even necessary. See http://www.codechef.com/viewsolution/2976638 (AC in 0.00 s)

1 Like

भाई इतना माथा मारने की तो जरुरत ही नहीं थी |

4 Likes