### ayushanshul07's blog

By ayushanshul07, history, 5 weeks ago,

1985G - D-Function

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

• 0

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by ayushanshul07 (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   0 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!!
•  » » 5 weeks ago, # ^ |   0 Understood, thanks!