It's combinatorics based question. You need to use venn diagram to visualize it, basically there are 10**n (0,...9) ways to fill the array till N but there will be some cases where you need to fulfill the requirements i.e there will be some permutations which do not include "0" or "9", try to understand that case by simple venn diagram. the answer will be 10**n(total permutations) — 9**n(where there is no 9) — 9**n (where there is no 0) + 8**n (the intersection of prev. two cases);

• First assume there is no restriction whatsoever on the digits to place. In this case have n places to fill and all the 10 digits from 0 to 9 can be considered for each place. So the number of possible sequences is 10 * 10 * 10 ...up to n times i.e. 10^n. ( ^ stands for power). So this is basically the universal set containing all possible sequences. Hence, it is trivial that we need to discard certain sequences from this universal set in order to reach the desired answer.

• The restrictions given say that we need to have atleast one place each for 0 and 9 . So the complement (or, reverse scenario for that matter) of this restriction would be those sequences that DO NOT have any 0's or 9's in them. If you observe carefully we have to discard these sequences from the universal set.

Now let's see how can we evaluate this discarded quantity:

• If we remove a single digit from the digits we are given initially, we are left with 9 digits. So, using 9 digits to form our sequences means that we have discarded a digit, which can be either 0 or 9 . Hence we have 2 such cases — one where have discarded the digit 0 and the other where we have discarded 9 . Observe that for both cases we have a choice of 9 digits for each of the n places to be filled, so the number of such sequences would be 9 * 9 * 9...upto n times , i.e. 9^n. Since we have two cases, the total number of such sequences = 2*(9^n).

• so our answer till now = 10^n - 2*(9^n)

However, we have made a slight mistake, we have doubly counted the case where both 0 and 9 are not present in the sequence (i.e the intersection set of the aforementioned two cases). So we need to add that set once back to the result. Now here we are discarding both digits 0 and 9 so we are left with 8 digits. Following what we have done so far, it is easy to see that this set has cardinality = 8^n.

• this means our final answer = 10^n - 2*(9^n) + 8^n, and by the problem, we need to provide the answer modulo 1e9+7 so we do so accordingly.

And for the latter part of your post, this problem was based on what is known as Principle of Inclusion and Exclusion.

Hope that helps :)