Find out which number from 1 to N is missing from a list with N - 1 numbers

Question

Write a function that, given a list of N 1 integers numbered from 1 to N, finds out which integer of that range is missing.

Input: The input parameter is an L list of size N 1 containing integers (no repeated) from 1 to N.

Output: The function must return the integer number x which belongs to the range [1, N] but which does not belongs to the input list L.

Examples

Input: [3,1] Output: 2 Input: [1,2,3,5] Output: 4 Input: [2,4,3] Output: 1

    def quebracabecas(lista_pecas):
        i = 1
        while i < len(lista_pecas):
            if i not in lista_pecas:
                return 
            contador += 1
        return lista_pecas

Answer 1

Given the constraints of the problem and the fact that there is no need to validate the list (that is, I can trust that the numbers are between 1 and N and the list always has N - 1 numbers and there are no repeats), can be done in a way "smart".

The sum of all numbers between 1 and N is given by the formula of the sum of PA: N * (N + 1) / 2.

Therefore, I can calculate the sum of the PA (i.e., of all numbers from 1 to N), and from this value I subtract the sum of the elements from the list. The result will be the number that is missing:

def quebracabecas(lista_pecas):
    n = len(lista_pecas) + 1
    somatotal = n * (n + 1) // 2
    return somatotal - sum(lista_pecas)

print(quebracabecas([3, 1])) # 2
print(quebracabecas([1, 2, 3, 5])) # 4
print(quebracabecas([2, 4, 3])) # 1

Since the list has N - 1 numbers, just add 1 to its size to get the N.

Then I get the sum of all the numbers from 1 to N, using the formula already mentioned (I only used the whole division operator // so that the result is not a float, even because in the case of the sum of PA it is guaranteed that the result is integer then there is no danger of undue rounding).

Then simply subtract the sum of the elements from the list (obtained with sum).

---

Another (less efficient) alternative is to sort the list and then see which one is missing:

def quebracabecas(lista_pecas):
    valores = sorted(lista_pecas)
    for i in range(len(valores)):
        if i + 1 != valores[i]:
            return i + 1 # valor não corresponde à posição, retorna
    # se percorreu todos é porque o último é o que falta
    return len(valores) + 1

After sorting the list, just see if the first element is 1, the second is 2, etc. What does not match the position is what is missing.

Answer 2

I would so use a create a set with the range of your input array, and use it to check which item is missing, the big O is not very good but for troubleshooting the problem and for small datasets I believe this ok

def quebracabecas(lista):
    teste_set = set(range(lista[0],lista[-1]))
    for i in lista:
        if i in teste_set:
            teste_set.remove(i)
        
    return teste_set