Einfach 2 gelöst 66.7% Erfolgsquote

Missing Number

Find the one number missing from 0..n.

Das lernst du

  • Compute the expected sum of 0..n
  • Find the missing value from the difference
  • Solve it in one pass without sorting

Problem

Übersetzung anzeigen

The list holds n distinct numbers taken from 0, 1, …, n, so exactly one number in that range is missing. Find it. (Hint: compare the expected total with the actual total.)

Implement missing_number(numbers).

Input

numbers: n distinct numbers from 0 to n.

Output

Return the missing number.

Einschränkungen

0 ≤ n ≤ 100,000

Beispiele

Beispiel 1
Eingabe:
numbers = [3, 0, 1]

Erwartete Ausgabe:
expected = 2
Eingabe:
std::vector<long long> numbers = {3, 0, 1};

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long[] numbers = new long[] {3, 0, 1};

Erwartete Ausgabe:
long expected = 2;

Erläuterung

n = 3, so the range is 0–3; 2 is missing.

Beispiel 2
Eingabe:
numbers = [0]

Erwartete Ausgabe:
expected = 1
Eingabe:
std::vector<long long> numbers = {0};

Erwartete Ausgabe:
long long expected = 1;
Eingabe:
long[] numbers = new long[] {0};

Erwartete Ausgabe:
long expected = 1;

Erläuterung

n = 1 and the range is 0–1; 1 is missing.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

The numbers should match the full range from 0 through n except for one hole.

Hinweis 2

Compare what the complete range would total against what the list actually totals.

Hinweis 3

Watch for the case where the missing value is 0 or n.

Erwartete Komplexität

O(n) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 HJhettory Jurash Python 784 ms - 4/5 Code ansehen
2 KKKaneki Ken Python 874 ms - 3/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 2 vollständige Lösungen unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.