# Even-Odd Problem - CODE OF GEEKS

@shubham_avasth Sir, can you give me any direction on how to proceed for this problem? I observe that even length numbers are to be ignored.So what shall be the approach for the remaining odd length numbers?

DP on digits

This is a digit DP question. You can write a function that solves the question for range [0, x]. Using this function find the answers for the ranges [0, R] and [0, L], then subtract them to find the final answer.

Just read a blog about the topic. The one posted by @ajaymalik is good as well. The approach is standard and coming up with the solution will be straightforward once you read a blog about the topic.

from here u can get the code, enjoy

@shubham_avasth
I got stuck while doing this question with digit dp , can u give me some hint how to do it.

what will be its time complexity?

Let’s assume you want to find the answer for a range [0, 3456].
You find the solutions for the the sets of numbers of the following forms and sum them up to get the final answer:-

1. 0\square\square\square
2. 1\square\square\square
3. 2\square\square\square
4. 30\square\square
5. 31\square\square
6. 32\square\square
7. 33\square\square
8. 340\square
9. 341\square
10. 342\square
11. 343\square
12. 344\square
13. 3450
14. 3451
15. 3452
16. 3453
17. 3454
18. 3455
19. 3456

You don’t necessarily need to fill up a DP table to solve this question though.

O(10 \times \log_{10} R + 10 \times \log_{10} L) = O(\log R)