| # | User | Rating |
|---|---|---|
| 1 | tourist | 3843 |
| 2 | jiangly | 3705 |
| 3 | Benq | 3628 |
| 4 | orzdevinwang | 3571 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3530 |
| 8 | ecnerwala | 3499 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 164 |
| 3 | awoo | 163 |
| 4 | TheScrasse | 156 |
| 5 | nor | 153 |
| 6 | maroonrk | 152 |
| 6 | -is-this-fft- | 152 |
| 8 | Petr | 145 |
| 9 | orz | 144 |
| 9 | pajenegod | 144 |
For numbers with l+1 digits, there are floor(9/k) + 1 (say a) options per digit, hence the total number of numbers should be a^(l+1). Similarly, for l+2 digits, a^(l+2). So on for r digits, a^(r).
Shouldn't the answer be the sum of these numbers?
a^(l+1) + a^(l+2) + .... + a^r
Auto comment: topic has been updated by ayushanshul07 (previous revision, new revision, compare).
say l =3 , r =5; means your n will be between 1000 and 100000 1000,1001,1002...1999,... ,99999 will be your probable numbers out of which the valid numbers must have each digits lesser than or equal to 9/k. now say we didnt have a lower limit r then the valid answer would have been : a^r , but we have a lower bound l so we over counted those numbers so we can just do -a^l, final answer being a^r -a^l.
why your approach is wrong : a^r is the number of valid numbers till number of digits are r thats simple catch you missed. so you basically are over counting. why does a^r include all valid numbers upto r digits : since you are also counting 0 as valid digit hence we can get all r-1 , r-2, ... 1 digit numbers too!!
Understood, thanks!