Comment by hyperion2010 | Hacker News Reader

Comment by hyperion2010 | Hacker News Reader

Parent Full thread

So I see a number of replies that say 'add the list up' but there is no list. There are no spaces, you would have to add in the spaces yourself which is an extremely difficult problem.

Since there are no spaces in the list: 1) I would count the instances of didgits 0-9 2) compare those counts to the counts produced by the complete set of didgets 3) The ones that fell below in count are the didgits in the missing number 4) Count the instances of the permutations of your missing didgets 5) compare those counts to the counts from the full list 6) Done.

I just tried this -- you don't know _which_ combination is missing unfortunately in the case of a 2 or 3 digit number. With 3 you might be able to figure it out by using the limit of 250 (e.g. if 2 4 and 7 are missing there is only 1 to recombine them and have it be less than 250), but with two how do you differentiate between say 26 and 62 in a clever, non brute force way?

In case anyone wants a starting point:

  import random
  from collections import Counter
  
  rand_list = range(0, 250)
  random.shuffle(rand_list)
  
  missing = rand_list.pop()
  
  shuffled = ''.join([str(x) for x in rand_list])
  
  full_list = ''.join([str(x) for x in xrange(0, 250)])
  cntr = Counter()
  for digit in full_list:
      cntr[int(digit)] += 1

  for digit in shuffled:
      cntr[int(digit)] -= 1
  
  digits = []
  for k, v in cntr.items():
       for _ in range(0, v):
           digits.append(k)

Reply on news.ycombinator.com