Problema
A lista contém n números distintos escolhidos de 0, 1, …, n, então exatamente um número desse intervalo está faltando. Encontre-o. (Dica: compare o total esperado com o total real.)
Implemente missing_number(numbers).
Entrada
numbers: n números distintos de 0 a n.
Saída
Retorne o número que está faltando.
Restrições
0 ≤ n ≤ 100.000
Exemplos
Entrada:
numbers = [3, 0, 1]
Saída esperada:
expected = 2Entrada:
std::vector<long long> numbers = {3, 0, 1};
Saída esperada:
long long expected = 2;Entrada:
long[] numbers = new long[] {3, 0, 1};
Saída esperada:
long expected = 2;Explicação
n = 3, então o intervalo é 0–3; 2 está faltando.
Entrada:
numbers = [0]
Saída esperada:
expected = 1Entrada:
std::vector<long long> numbers = {0};
Saída esperada:
long long expected = 1;Entrada:
long[] numbers = new long[] {0};
Saída esperada:
long expected = 1;Explicação
n = 1 e o intervalo é 0–1; 1 está faltando.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Os números devem cobrir o intervalo inteiro de 0 até n, exceto por uma lacuna.
Dica 2
Compare o total do intervalo completo com o total real da lista.
Dica 3
Fique atento ao caso em que o valor faltando é 0 ou n.
Complexidade esperada
tempo O(n), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.