1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.