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

  • 1
    Why do you "need" a formula?2012-11-01
  • 0
    Basically I have to write a program to calculate the answer. I have a different approach where I individually check ever number between the range for given condition, but its a very slow and time consuming approach.2012-11-01
  • 3
    It seems that you are asking [this](http://www.codechef.com/NOV12/problems/DDISH) 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**.2012-11-05
  • 1
    Flagged my own answer for deletion. I see no "otherwise" in this situation; clearly the proposer has already cheated and should be disqualified.2012-11-06
  • 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?2012-11-06
  • 0
    @WillieWong If outside help on this problem is cheating according to the contest rules, then I don't want anyone using my answer to do so. For the OP, I can only hope s/he withdraws from the competition.2012-11-06
  • 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?2012-11-06
  • 0
    @B.D: I agree with WillieWong; please restore your answer, at least after the competition. I am sure there are others from the competition who have seen your answer and now have an advantage over those who have not. Restoring your answer might level the playing field, but it would also keep other competitors from discovering the answer for themselves. I can see arguments for and against restoring before the end of the competition.2012-11-06
  • 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.)