@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:-
- 0\square\square\square
- 1\square\square\square
- 2\square\square\square
- 30\square\square
- 31\square\square
- 32\square\square
- 33\square\square
- 340\square
- 341\square
- 342\square
- 343\square
- 344\square
- 3450
- 3451
- 3452
- 3453
- 3454
- 3455
- 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)