3 ms·
if all the numbers from 1 to 250, but one, were written in random order (no spaces) how would you find the missing number? FOR EXAMPLE, 132456789101113 is 1-13
by andrewcooke 13y ago
if all the numbers from 1 to 250, but one, were written in random order (no spaces) how would you find the missing number?
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]
- deleted 13y ago[deleted]
- brown9-2 13y ago"1" is going to match a lot of numbers that aren't 1.
- untitledwiz 13y agoAdd them all up, subtract that from the actual sum of 1-250 and voila. Optimization bonus: you don't need to do the second sum, there's a closed form (I don't remember what it is, but I do remember Gauss came up with it as a kid).
- taeric 13y agoDoesn't this only work if you have spaces between the numbers?
- seniorsassycat 13y agoandrewcooke supposed the numbers were not separated by spaces so 1727321173475 could be 1, 72, 73, 211, ... or 17, 27, 32, 117, ... or 172, ...
- cocoflunchy 13y agon(n+1)/2
- andrewcooke 13y agono spaces. 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
- deleted 13y ago[deleted]
- anonymoushn 13y ago# 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)
- msandford 13y agoIf there were spaces between the numbers, yeah. Here's the difference: 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
- andrewcooke 13y agooh, good point. thanks (although i think "no spaces" was in there from the start, it wasn't an edit...)
- deleted 13y ago[deleted]
- oh_sigh 13y agoAdd all the numbers in the list up, and then subtract that value from the sum of 1 to 250. That value is the missing number, in O(n) time and O(1) space. This only works if all the numbers are only written once though.
- yelnatz 13y agoCan't just do that right away since you have to parse the string first: ...11123... Is that a 1, an 11, a 12, a 112, a 123?
- jffry 13y agoSum all the individual digits of 1-250 (e.g. 11 is 1+1 is 2). Sum all the individual digits in your string. Now you at least know the sum of the missing digits, and how many missing digits there are.
- deleted 13y ago[deleted]
- deleted 13y ago[deleted]
- taeric 13y agoI would think you could start with assuming that all numbers are used, so you know how many of each digit you should see. Calculating how many of each digit you actually saw should give you a list of which digits were not seen. Then, you should have a much smaller search for the permutations of the missing digits. (This make sense?) I'm ridiculously curious to know if there is a clever trick to this! :)
- XenithShade 13y agoClosed form is ((1 + 250)* 250)/2 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
- woofyman 13y agoCreate an array of 250 booleans. Go through the list 3 times. First all the 1 digit numbers, then the 2 and 3 digit numbers. Set the array entry for the resulting numbers to true. The entry that is false is the missing number.
- mbell 13y agoI'm sure there are faster ways but a quick and dirty approach would be to count how many of each digit are in the input string, then compare to the expected result, which is easy to figure out. This will tell you what digits are missing from the input. There will be at most 3 of them, then just search the input for the possible valid combinations of those digits, as soon as you find one that is missing, you're done.
- hyperion2010 13y agoSo 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.
- tcas 13y agoI 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)
- msandford 13y agoMy quick take on it is that you have to generate a list of all the 1-tuples, 2-tuples and 3-tuples in that very long string, along with the start and end indexes of each tuple. 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.
- deleted 13y ago[deleted]
- CamperBob2 13y ago"Gee, that's an ugly way to store numbers. Where did this data set come from? What business process generated it, and under what constraints? Can I talk to the guys who own that process?"