# Why digits in between doesn't change the difference sum and only 1st and last digit matters

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.

1. How is this possible that $\lvert W \rvert \le 9$
2. 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?

• If you expand $\sum_{i=2}^N (D_i - D_{i-1})$ it is pretty clear why $|W|\leq 9$. Have you tried? – Marco Bellocchi Apr 18 '18 at 10:22
• It seems to but by many examples I tried but I can't figure out more technically why. – Brij Raj Kishore Apr 18 '18 at 10:23
• $\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$ – Marco Bellocchi Apr 18 '18 at 10:26
• @MarcoBellocchi How could I missed that. Thanks. But I still got my 1st question answer. – Brij Raj Kishore Apr 18 '18 at 10:28
• Got it both answers @MarcoBellocchi. Thank you. Please write your answers in answer section so I can accept it. – Brij Raj Kishore Apr 18 '18 at 10:47

## 1 Answer

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.