Tutorial :how to find distinct digit set numbers over a range of integers?



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
Previous
Next Post »