1
$\begingroup$

Given M digits which are between 1 to 9, Find the number of ways to form N digit number, by repeating one or more given digits such that each of M digits are present in N digit number at least once. Example if M = 3 and N = 4 Answer is 36.

Explanation - let the three digits be 1 2 3 our N = 4, digit number can be 1123, 3211, 1132, ..... repeating 1 similarly repeating 2 and three we will get the total ans.

Since answer is large find the ans % 10000000007. 1 ≤ M ≤ N ≤ 100.

$\endgroup$
  • 1
    $\begingroup$ Is this a project Euler problem? $\endgroup$ – rogerl Oct 2 '14 at 23:26
  • $\begingroup$ nope its from a contest that was held in September, code.google.com/codejam/contest/4214486/dashboard#s=p0 $\endgroup$ – Ashesh Vidyut Oct 2 '14 at 23:28
  • 1
    $\begingroup$ For each specific case (at least small ones) I'd recommend inclusion-exclusion. However, I am not too familiar with coding contest problems, so I don't know what methods would work well there (you'd need to handle more general cases, but you have more number-crunching ability compared to the common by-hand problem) $\endgroup$ – Arthur Oct 2 '14 at 23:35
  • $\begingroup$ Do the repeated digits have to be adjacent? In your examples, you include 1123 and 3211, but not for example 1231. $\endgroup$ – rogerl Oct 2 '14 at 23:45
  • 1
    $\begingroup$ Non mathematical way would be dp+bitmask. the dp is like plugging characters to the right and setting on the digits that have been used. That assuming that M<10. $\endgroup$ – Phicar Oct 3 '14 at 2:21
0
$\begingroup$

If I understand this correctly it is a familiar problem, equivalent to the problem of counting the number of $N$-letter words from an alphabet of size $M$, with the restriction that each letter is used at least once.

The well-known answer is $M!S(N,M)$, where $S(N,M)$ is the Stirling number of the second kind, counting the number of ways to partition $[N]$ in $M$ parts. You can find references about these Stirling numbers like recursive formulas and generating functions all over the place if you actually need to write a program that produces the answer for concrete values of $M$ and $N$.

Btw, a Java implementation using a simple summation for these Stirling numbers calculates e.g. $S(200,100)$ in a fraction of a second (although it has over 200 digits), so performance cannot be a problem for the values you mention.

$\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.