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:

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.

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…