You are given to integers L and R. Find the number of integers which have the last digit as 2, 3 or 9 and lie in the range [L, R].

Explanation

As the constrainsts are small on L and R, we can pre-calculate all good numbers. Then each test case just asks to find out how many good numbers lie within the given range. This can be easily answered using prefix-sums. If you donâ€™t know about prefix-sums, you can read it here. Basically the idea is the following:

\sum_{i=l}^{i=r} A_i = \text{(Prefix-sum at i=r)} - \text{(Prefix-sum at i=l-1)}

Below is a pseudo-code for it:

def init():
for i in [1, 1000000]:
last_digit = i % 10
if last_digit == 2 or last_digit == 3 or last_digit == 9:
good[i] = 1
else:
good[i] = 0
# Build prefix sum
for i in [1, 1000000]:
good[i] += good[i-1]
def solve(l, r):
ans = good[r] - good[l-1]
return ans

The time complexity of the above approach will be O(N + T), where N = 100000 is for pre-computation and T is for answering every test case in O(1) using prefix-sums. The space complexity of the above approach will be O(N) for storing the prefix array of good elements.

Bonus Problem

Solve the problem without any pre-computation and in O(1) memory.

Idea:

Click to view

Note that every consecutive number from â€śxâ€¦0â€ť to â€śxâ€¦9â€ť has 3 good numbers.

Feel free to share your approach, if it was somewhat different.

Wtfâ€¦ I wasted a lot of time on this question due to some connection issue and due to some problem with codechef IDEâ€¦
Didnâ€™t knew that 1st question is that low in div2 (as I was in div2 before contest and I was in div1 before previous contest)â€¦
This is completely brute Forceâ€¦

@l_returns Pro tip #1 (#nooffence) Never use codechef ide in short contest for testing soln. It will ~1 min to give verdict. And sometimes it also shows â€śSubmission Limit Reachedâ€ť . Alternative offline ide(Best Option), CodeForces Ide (A bit slower but can be used) both are relatively faster. I personally use these options for testing purpose.