# arr must contain all of the numbers from 1 to k except one
# returns the number which is missing
def missing_number(arr):
return ((len(arr)+2) * (len(arr)+1))/2 - sum(arr)
I can't really talk about the article, since it is down :(Edit to reflect edit in the parent: The problem as posed is not soluble in general. For k=21,
1 2 12 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 (21 is missing)
==
1 21 2 3 4 5 6 7 8 9 10 11 13 14 15 16 17 18 19 20 (12 is missing)
You can discover the missing digits in linear time, but determining from there whether the input has a unique solution seems a bit annoying.If a valid permutation of the missing digits is missing, you win, but you can have a unique solution without that being the case:
11 21 13 3 2 4 5 6 7 8 9 10 14 15 16 17 18 19 20 1 (12 is missing)1 2 3 4 5
12345
At this level it's no big deal. What happens when you get to double digits?
11 12 13
111213
Now what happens when they're not in a nice order?
5121892178
...11123...
Is that a 1, an 11, a 12, a 112, a 123?
but you can get the formula by imagining the numbers as piles of pennies and then completing them to make a square and then splitting down the diagonal
*
**
***
*..
**.
***
\.. \
*\. + \
**\ \
where a \ is half a penny. so * = \\so it's 1/2 * n * n (ie half the square) plus an extra 1/2 for each one on the diagonal.
so it's n * n/2 + n/2 = (n+1) * n/2
1727321173475
could be 1, 72, 73, 211, ... or 17, 27, 32, 117, ... or 172, ...
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.
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)Then you find a set of tuples which cover 1-250 (missing one number) and which don't overlap.
You can start by filtering out all the 3-tuples which are over 250.
I might use a hash table to put together a list of all duplicates. Any hash table entry with no duplicates has to be right. Use the indexes that have been removed from the "eligible" pool to remove tuples from the hash table. Iterate.
Of course it's entirely possible that iterating like that could still leave you without a solution. At which point a guess has to be made and to continue solving. If said guess is bad, backtrack and make a different guess.
Obviously it's harder to implement than to outline. And I've probably missed a bunch of optimization.
Once you know the actual sum, you can do it either: sum all, subtract total - sum. Or with data structures: it would be a variant of the "given an array find all pairs of numbers that add up to a sum". The benefit of using the data structure approach would be that you can now find x missing numbers in the range 1 - 250.
note* the closed form might have a off by one error
I'm ridiculously curious to know if there is a clever trick to this! :)
FOR EXAMPLE, 132456789101113 is 1-13 and not very random. most answers below have misunderstood me (well, less now that some have been deleted in shame... ;o)
you can get the digits, just by seeing what is missing. but then you seem to be left with a rather tricky partition problem. so i guess dynamic programming? is there a better way?
would it help to pick out unique combinations (if the pattern 249 occurs just once, it must be 249, unless it is the missing number)? how far would that get you?
i guess since you know the missing digits you should check for each permutation - you might get lucky and not find one.
is there some cute trick? something involving suffix trees?
[edit: anonymoushn has a good point - it's not guaranteed unique]