3 ms·
# 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(
by 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...)