I need a little help, a have a list of integers - the difference between the consecutive elements is constant, but the list is unsorted and one element is missing. The function takes a list as an input, the output is an integer (the missing one).

I wrote this code:

def missing_number(lst):
    lst.sort()
    diff = lst[1] - lst[0]
    for i in range(len(lst)-1):
        if lst[i 1] - lst[i] != diff:
            return int(lst[i]   diff)

It's working for this case: assert missing_number([1, 4, 2, 5]) == 3, but I can't make it work for a case like this: assert missing_number([2, 6, 8]) == 4 - the difference is more than 1 digit - it's returning 10.

CodePudding user response：

It doesn't like your code is not working as expected for difference is more than 1 digit. It is purely because of sequence. If you try the differ sequence with more with your code, it gonna definitely work. Eg:assert missing_number([2, 4, 8]) == 6

So you can not take difference between 1st 2 numbers. You have to take the minimum difference, so you can check by comparing difference with next 2 numbers & take the smallest.

You can try:

def missing_number(lst):
    lst.sort()
    final_diff = 0
    diff0 = lst[1] - lst[0]
    diff1 = lst[2] - lst[1]
    if diff0 < diff1:
        final_diff = diff0
    else:
        final_diff = diff1

    for i in range(len(lst)-1):
        if lst[i 1] - lst[i] != final_diff:
            return int(lst[i]   final_diff)

print(missing_number([2, 6, 8]))

output:

4

CodePudding user response：

A linear time solution: Compute the sum you'd expect if the number weren't missing, and subtract the actual sum:

def missing_number(lst):
    expect = (min(lst)   max(lst)) * (len(lst)   1) // 2
    return expect - sum(lst)

The expected full sum is the average (which is (min max)/2) multiplied by the number of numbers (which is len 1). I postpone the division until the end since min max might be odd.

Yours fails the example [2, 6, 8] because you compute diff = 4, but it should be 2. You can't just always use lst[1] - lst[0]. You could for example use (lst[-1] - lst[0]) // len(lst) instead.

CodePudding user response：

1. First, you have to sort your list as u did.
2. Create a new list called diff which contains the difference between consecutive elements in the input list.
3. Find the index of the maximum value in the diff list. (Since the input list is sorted, and the difference between the missing element and the next element is always the largest, the max value in the diff list should be the difference between the missing element and the next element.)
4. Calculate the missing number by adding half the maximum difference to the number at the index found in step 3.
5. Return the results.

It’s not the most efficient way to solve this problem but similar to yours as it also creates a new variable with diff. list.

def missing_number(lst) :
    lst.sort()
    diff = [lst[i 1] - lst[i] for i in range(len(lst) - 1)]
    idx_max = diff.index(max(diff))    
    result = lst[idx_max]   int(max(diff) / 2)
    return result