### PROBLEM LINK:

### DIFFICULTY:

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 <= 10^{10}

### 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 10^{10}. 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