Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
Can you explain this a bit more deeply? I don't quite understand. –  DJDavid98 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. –  DJDavid98 Feb 18 '13 at 18:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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