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.

@shubham_avasth @ajaymalik thanks to both Sirs for your speedy reply…

from here u can get the code, enjoy :slight_smile:

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)