Problem Link
Author: Ivan Safonov
Tester: Hasan Jaddouh
Editorialist: Bhuvnesh Jain
Difficulty
CAKEWALK
Prerequisites
Prefix sums
Problem
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:
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.
Time Complexity
O(N + T)
Space Complexity
O(N)