I got this question on codechef contest and now the contest has already ended. Here is the question
Consider an integer with N digits (in decimal notation, without leading zeroes)
$ D_1, D_2, D_3 ... D_N $. Here $D_1 $ is the most significant digit and $D_N$ is the least significant digit. The weight of the integer is defined as $$\sum_{i=2}^N (D_i - D_{i-1})$$
You are given $N$ and $W$ . Find the number of positive integers with $N$ digits (without leading zeros) and weight equal to $W$ . Compute this number modulo $10^9+7$.
Constrainsts
- 1 $\le T \le 10^5$
- $2 \le N \le 10^{18}$
- $\lvert W\rvert \le 300$
I was able to figure out the solution and it got accepted. I was able to do so because I have generated test cases for small cases and recognized the pattern. But I have 2 questions.
- How is this possible that $\lvert W \rvert \le 9$
- By the pattern I was able to find out that we have to fix the first and last digit of a $N$ digit no. and count the possibilities of those two number depends on the weight required. And we can arbitrarily choose any $N-2$ digits in between.
Now for example $N=4, W = 7$ I have to fix 1st and last digits such that their difference is 7. So the possibilities of $D_1 = 1, 2 $ and $D_N = 8,9$ correspondingly. And remaining two digits I can choose in $10 \times 10 $ So the answer is $2\times 10\times 10$. Why this was working?
As per comment, the key part is to note that $$\sum_{i=2}^N (D_i - D_{i-1})=D_2-D_1+D_3-D_2+...+D_N-D_{N-1}=(D_2+D_3+D_4+...D_N)-(D_1+D_2+...D_{N-1})=D_N-D_1$$
And for the first question answer we can deduce from above that $D_N - D_1$, the minimum and maximum value can be at $D_N = 9 , D_1 = 0 $ i.e. $-9$ and $D_N = 1, D_1 = 9$ i.e. $8$ so the range of $W$ is $[-9,8]$. Or $-9 \le W \le 8. $ Glad it helped.