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.

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

share|improve this question
1  
Why do you "need" a formula? –  Graphth Nov 1 '12 at 15:13
3  
It seems that you are asking this problem from a running online contest. It directly violates the terms of Codechef. Please try to solve any problem by yourself at first and ask for help when the contest is over. Otherwise it will be considered as cheating. –  mostafiz Nov 5 '12 at 7:59
1  
Flagged my own answer for deletion. I see no "otherwise" in this situation; clearly the proposer has already cheated and should be disqualified. –  Benjamin Dickman Nov 6 '12 at 8:30
2  
@B.D: I am not sure deletion is necessary: now that the cat is already out of the bag, wouldn't it be better to leave it up so that the OP is not the only one benefiting from your answer? –  Willie Wong Nov 6 '12 at 11:41
1  
@B.D. in which case wouldn't it be better to just contact CodeChef and tell them about it, so they can remove this question from their contest? They seem to be adding questions mid contest too. Also, will you restore your answer on November 12, when the contest ends? –  Willie Wong Nov 6 '12 at 11:53

1 Answer 1

up vote 3 down vote accepted

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.)

share|improve this answer

protected by Community Jan 28 '13 at 20:26

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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