Fácil 2 resolvidos 66.7% de aceitação

Número Ausente

Encontre o único número faltando em 0..n.

O que você vai aprender

  • Calcular a soma esperada de 0..n
  • Encontrar o valor que falta pela diferença
  • Resolver em uma passada sem ordenar

Problema

Ver original (inglês)

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

Exemplo 1
Entrada:
numbers = [3, 0, 1]

Saída esperada:
expected = 2
Entrada:
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.

Exemplo 2
Entrada:
numbers = [0]

Saída esperada:
expected = 1
Entrada:
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 HJhettory Jurash Python 784 ms - 4/5 Ver código
2 KKKaneki Ken Python 874 ms - 3/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 2 soluções completas abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.