Author: Ivan Safonov
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain
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].
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:
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.
Solve the problem without any pre-computation and in O(1) memory.
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.
O(N + T)