flash_7's blog

Problem with the recurrence relation of a dp problem
By flash_7, history, 9 years ago, In English

Given two decimal numbers U and V if we write down all the numbers from U to V how many zeroes(0) we will write?Where U<=V<=10^9 For example if U = 100 and V = 105 then we have to write 100,101,102,103,104,105 There are total 7 zeroes therefore the result is 7. I was trying to find a pattern but i could not come up with any perfect solution :(

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you don't need dp for this.. the number of zeroes between 10n and 10n + 1 - 1 = 9 * n * 10n - 1

Just wrote python script to find this, I'm very bad in number theory :(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But how does it work?Can you please explain a bit?

    → Reply