###

Question:

Suppose i have a unsigned integer, call it low and one another call it high such that high>low. The problem is to find distinct digit set numbers over this range. For example, suppose low is 1 and high is 20 then the answer is 20, because all the numbers in this range are of distinct digit sets. If suppose low is 1 and high is 21, then the answer is 20, because 12 and 21 have same digit set i.e.1, 2. I am not looking for a bruteforce algo., if anyone has a better solution then a usual bruteforce approach, please tell..

###

Solution:1

There obviously is a mathematical answer to this, although I'll admit that I haven't worked it out as yet.

Simply put if the low = 1 and high = 99 then we have the following:

`0 - 9 = 10 unique numbers 10-19 = 10 unique numbers 20-29 = 9 unique numbers 30-31 = 8 unique numbers 40-49 = 7 unique numbers 50-59 = 6 unique numbers 60-69 = 5 unique numbers 70-79 = 4 unique numbers 80-89 = 3 unique numbers 90-99 = 2 unique numbers `

It would perhaps be easier to work out if we assumed that all numbers had to have the same number of digits, with leading zeros where required. For example 01, 02, 03, 04 for 1, 2, 3, 4. This would mean that 01 and 10 would match. Then our number distribution changes to:

`0 - 9 = 10 unique numbers 10-19 = 9 unique numbers 20-29 = 8 unique numbers 30-31 = 7 unique numbers 40-49 = 6 unique numbers 50-59 = 5 unique numbers 60-69 = 4 unique numbers 70-79 = 3 unique numbers 80-89 = 2 unique numbers 90-99 = 1 unique numbers `

You can see that it should be possible to base a recursive formula on this using factors of 10 to determine how many unique numbers there may be. The difficulty will be how to cope with the starting and ending points being variable e.g. low = 25 and high = 87. Still this is a start, I'll think further on it.

###

Solution:2

I think I finally wrapped my head around the problem.

Let's take range `[low,high]`

and put the numbers within this range in sets depending on their digits as such:

- "121" --> set "112"
- "122" --> set "122"
- "211" --> set "112"

We want to know the number of sets that will contain a unique element.

I would suggest that the simplest way to do this is actually... to do it like this.

`def rangeCount(low, high): sets = defaultdict(list) for i in range(low, high+1): key = `i`.sort() # obtain digits and sort them sets[key].append(i) count = 0 for v in sets.values(): if len(v) == 1: count = count + 1 return count `

Okay, it's bruteforce, but at least everybody should be on the same page now :)

###

Solution:3

Maybe this will get you started: mathematic combinations

http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117

**Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com**

EmoticonEmoticon