2
$\begingroup$

I need a formula to find out the total number of positive integers with distinct digits within a given range. Ex: Numbers $231, 123, 259$ have distinct digits while $211, 101, 332$ do not.

Example: 1) range $5$ - $13$ Here all numbers between $5$ to $13 $ except $11$ have distinct digits. So, Answer= $8$.

2) range $1$ - $100$ Answer = $90$.

  • 0
    You might be interested in my answer in another question: http://math.stackexchange.com/a/332702/68762013-03-17

1 Answers 1

4

You might make use of the following sequence: "Number of n-digit positive integers with all distinct digits."

For example, if you are checking for numbers with distinct digits between 172 and 407,135, you can use the above sequence to immediately account for all numbers with distinct digits that have length 4 or 5, i.e., in the range 1,000-99,999 (from the sequence: 4536 + 27,216) and then you could brute force 172-999 and 100,000-407,135, and simply add these to your total. This might save a bit of time, e.g., for checking 5 through 9,813,253,164.

Also, an observation to incorporate into your program:

If I'm checking five digit numbers and I get to 13,300, then the next number to check should definitely not be 13,301. (Maybe it should be 13,400, but there's no point in checking 13,301, 13,302, 13,303, ..., 13,399; those two 3's have already disqualified all of these numbers.)

In any event, once the strings have eleven digits they can't all be distinct (pigeonhole property, since we are in base 10) so the numbers to be dealt with here are relatively small for a computer. (In other words, even a poorly written program should run pretty quickly.)