# Counting the amount of N digit numbers made from K digits divisible by X.

Look at the problem from this way:

N is a number, for example it's 4.
K would be an array of digits, like: [0, 1, 2, 3]
X is again, a number, let's say it's 11.

How do I count the amount of numbers matching these circumstances?

How I am currently doing this is:

1. Create an array (I will call it allnumbers) of all numbers between the smallest possible number made with the specified digits from K (== 1001) AND the biggest possible number created using the highest digit from K, repeated as many times as the amount of N (== 3333) that are divisible by X.
2. Eliminate/remove all numbers from the allnumbers array that contain different digits from the ones specified under K
3. Return the length of allnumbers as the amount

I believe the final answer is 34.

## 1 Answer

Your approach is fine. You can be more efficient by combining steps 1 and 2, only generating numbers that contain the proper digits. You can use a set of nested loops, each running $|K|$ times. If $K$ were $\{3,5\}$ you would generate $3333, 3335, 3353, \ldots 5555$ Depending on $X$, you can be more clever and not do step 3. If $X=2,$ only take even digits for the ones digit. In some cases you can prove that $\frac 1X$ of the $|K|^N$ numbers are divisible by $X$ and you don't have to generate the numbers at all. If $K$ were all digits, you would have $0000$ through $9999$ and we know that $\frac1{11}$ of these, $910$ of them are divisible by $11$ without checking each one.

• Can you explain this a bit more deeply? I don't quite understand. – SeinopSys Feb 18 '13 at 17:54
• @DJDavid98: Did this help? If you still have questions, it would help if they were more specific. – Ross Millikan Feb 18 '13 at 18:25
• Close enough, thanks. – SeinopSys Feb 18 '13 at 18:41