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.


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.

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

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.