Can you give me tips on writing this better? This code works fine, but I know it's not "Pythonic" and anybody with coding knowledge would laugh at it. You're supposed to enter a list of integers and return the integer that is missing from the algorithmic equation. So [1, 2, 4, 5] would equal 3 and [2, 4, 8] would equal 6. I'm just learning for fun, this isn't homework or something.
len(items) doesn't ever change, so you don't have to verify len(items)>2 every time you run the loop. you can also write that range without the 0 and 1 and python will assume the range starts at 0 with step 1
items.sort()
num_diff = items[-1] - items[-2]
if len(items) > 2:
for i in range(len(items)):
if items[i] + num_diff not in items:
return items[i] + num_diff
you could make it more pythonic by iterating over the list instead of the range
if len(items) > 2:
for it in items:
if it + num_diff not in items:
return it + num_diff
a question though, what if the missing number is right between the last two numbers? your algo assumes the difference between the numbers must be that between the last two, no?
>a question though, what if the missing number is right between the last two numbers?
Absolutely no idea. The preconditions are only that items must be longer than 2 and that the missing element must always be between two elements in a sequence. Forgot to type. I'm a bit drunk now so I'm forgetful.
what if the list is empty? items[-1] would fail
from typing import List
def missing_number(items: List[int]) -> int:
if not len(items):
return 'Error: Empty list'
items.sort()
last = items[-1]
previous = items[-2]
diff = last - previous
for i in range(len(items)):
tmp = items[i] + diff
if len(items) > 2 and tmp not in items:
return tmp
if __name__ == '__main__':
print (missing_number([1,4,2,5]))
print (missing_number([2,6,8]))
print (missing_number([3,12,9]))
print (missing_number([8,20,16,12]))
def missing_number(items: list[int]) -> int:
if len(items) <= 2:
return nil
items.sort()
nd = items[-1] - items[-2]
for i,item in enumerate(items):
seq = item + nd
if items[i + 1] != seq:
return i+1, seq
this get ya hot and bothered?
for such a small function it doesn't matter much if you do it one way or another in terms of prettyness, but in terms of efficiency your code is O(nlogn) because of sorting, this could be done in linear time by for example finding lowest element and second lowest element, get their difference, then make a set of the input list (pythons sets are hash sets so insertion and element access are constant time), then do a for loop over range(min(list),max(list),step) and for each iterator value check whether it's in the list
would look like this:
def missing_no(l):
s = set(l)
smallest = min(s)
s.remove(s)
next_smallest = min(s)
step = next_smallest-smallest
for i in range(next_smallest, max(s), step):
if i not in s:
return i
[code]
also for the range function, if you give it 3 arguments like you have in your code then the arguments are first element, last element, step, you can also give it 2 arguments which gives step the default value 1 or you can give it one argument which also gives the first element the default value 0 so range(0,n,1) is the same as range(n)
and if you care about that then you might want some error handling on bad inputs like full sequences or empty lists, those don't return anything/give exception in the current code but if you know where the input comes from and it's definitely well formed I wouldn't add extra bloat for checking that
Have you passed an empty list or one with a single element to this function? Validate input and return/raise accordingly early before thinking about sorting or anything like that.
You probably shouldn't call items.sort() as this will mutate the original list outside of the function. Maybe check out the sorted built-in instead.
Just use for i in items:... instead of range if you only ever use the index to access the current value while iterating.
Probably shouldn't in-place sort the argument? /probably/? Absolutely do NOT mutate passed-in things like that, unless it is the specific, single, purpose of the function.
Got to be honest I'm only on week two of learning Python but these answers are scaring the hell out of me. Thanks for the advice.
this has a math solution, oneliner solution
like this?
missing_number = lambda l: (set(range(min(l), max(l), min(min([i for i in l if i != min(l)])-min(l), max(l)-max([i for i in l if i != max(l)]*~~) - set(l)).pop()
half of this is finding the step with accounting for the second or second to last element missing, that could probably be done easier, also this fails on empty/full lists
even better, assuming exactly one element is missing
missing_number = lambda l: [i for i in range(min(l),max(l)+1,(max(l)-min(l))//(len(l*~~ if i not in set(l)][0]
Assuming one integer is missing:
Sort list
Get length of the list (number of integers)
Subract the lowest integer in the list from highest (or the first element from last)
Divide the result by the lenth of list
Now you a have a number (X) that indicates the difference between two values in the list
Create new list with length+1, using first element + X
Subtract old list from the new list and you have your missing value
Here's a hint.
Take the differences between each consecutive pair in the sorted list. How can you use this to find out where the missing number is?
To make iteration easier you may want to make use of the standard library's itertools.pairwise function.
Solution:
sum(max(pairwise(sorted_items), key=lambda pair: pair[1] - pair[0])) / 2
I'll never manage to get spoilers right on this god forsaken site.
Anyways, there's also a divide and conquer solution here but then you start moving away from being pythonic.
You're choosing max, what if the missing element has a smaller difference?
They only work on certain boards.
Conversely, code tags don't work on other boards.
The difference between the elements surrounding the missing element will always be larger than other differences. Precisely speaking, it will be twice the common difference.
>Can you give me tips on writing this better?
Well...
> This code works fine
Oh. Then no, and none of the fine people in this thread gave you tips either.
Here is a tip though: anything that works - and I mean actually work in every way and for every input and isn't too slow or eat too much memory etc. - is as good as it will ever get. Problem is solved, now solve next problem instead of inventing more problems.
That's honestly good advice for 96% of programmers.
You need to be hellbent if you want to go further.
And also ready to potentially waste that time.