# 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* = 1
else:
good* = 0
# Build prefix sum
for i in [1, 1000000]:
good* += 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)