Count Even Numbers

Q: Wie prüft man im Code, ob eine Zahl gerade ist?

Prüfe, ob der Rest nach der Division durch 2 null ist: x % 2 == 0 . Das funktioniert in jeder gängigen Programmiersprache für positive Zahlen, negative Zahlen und null. Eine weitere Möglichkeit ist, das niedrigste Bit mit (x & 1) == 0 zu prüfen, da gerade Zahlen auf ein 0 -Bit enden.

Q: Ist null eine gerade Zahl?

Ja. Null geteilt durch 2 ist 0 ohne Rest und erfüllt daher die Definition einer geraden Zahl. Sie liegt außerdem zwischen den ungeraden Zahlen -1 und 1 , genau dort, wo eine gerade Zahl hingehört.

Q: Wie hoch ist die Zeitkomplexität beim Zählen gerader Zahlen in einem Array?

Ein Durchlauf mit einem Zähler benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Jeder Wert muss überprüft werden, daher ist keine Methode schneller als O(n) . Zuerst eine gefilterte Liste zu erstellen, ergibt dieselbe Anzahl, benötigt aber O(n) zusätzlichen Speicher.

EinsteigerArrays und Strings Mathe und Simulation

+10

Du erhältst eine nicht leere Liste von Ganzzahlen nums. Gib zurück, wie viele ihrer Werte gerade sind. Eine Zahl ist gerade, wenn bei der Division durch 2 kein Rest bleibt. Dazu gehören 0 und negative Zahlen wie -4.

Funktion

countEvens(nums: integer-array) → integer

numsinteger-array: die Liste der zu überprüfenden Ganzzahlen
Gibt zurückinteger: die Anzahl der geraden Werte in nums

Einschränkungen

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Beispiele

Eingabe: nums = [3, 8, 12, 5, 6]
Ausgabe: 3
Erklärung: 8, 12 und 6 sind ohne Rest durch 2 teilbar, während bei 3 und 5 ein Rest bleibt. Das ergibt 3 gerade Werte.

Eingabe: nums = [-4, -3, 0, 7]
Ausgabe: 2
Erklärung: -4 = 2 × (-2) und 0 = 2 × 0, also sind beide gerade. -3 und 7 sind ungerade, und die Anzahl beträgt 2.

Eingabe: nums = [1, 9, 15]
Ausgabe: 0
Erklärung: 1, 9 und 15 sind alle ungerade, daher zählt kein Wert und die Antwort ist 0.

+12 versteckte Tests beim Einreichen

Weiterführende Frage

Du erhältst viele Fragen der Form: Wie viele gerade Werte liegen zwischen dem Index l und dem Index r? Kannst du nach einem Durchlauf über nums jede Frage in O(1)-Zeit beantworten?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Schleife besteht aus einer Zeile; beim Test auf Geradzahligkeit scheitern die Lösungen. In vielen Sprachen ist der Rest einer negativen Zahl negativ, also ist -3 % 2 gleich -1. Der Test x % 2 == 0 ist für jedes Vorzeichen in jeder Sprache richtig, und ein laufender Zähler benötigt keinen zusätzlichen Speicher.

Sammle die geraden Werte und zähle sie.

Idee

Teile die Aufgabe in zwei Schritte auf: Wähle zuerst die geraden Werte aus und zähle dann, was du ausgewählt hast. Ein Wert x ist gerade, wenn x % 2 == 0. Die meisten Sprachen haben eine Filterfunktion, die die neue Liste in einer Zeile erstellt, und ihre Länge ist die Antwort. Für [3, 8, 12, 5, 6] lautet die gefilterte Liste [8, 12, 6], die Antwort ist also 3.

Das ist korrekt und gut lesbar, aber die neue Liste benötigt O(n) Speicherplatz – hier bis zu 5000 Werte –, nur um ihre Länge einmal auszulesen. Die Werte selbst werden nie wieder verwendet.

Algorithmus

Erstelle eine neue Liste, die jedes x in nums mit x % 2 == 0 enthält.
Gib die Länge dieser Liste zurück.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

Mit einem fortlaufenden Zähler zählen

Idee

Behalte statt einer Liste einen Zähler. Setze ihn auf 0, prüfe jeden Wert einmal und addiere 1, wenn der Wert gerade ist. Jeder Wert wird genau einmal geprüft, daher ist die Anzahl exakt, und der einzige Speicherbedarf ist eine ganze Zahl.

Beim Test ist Sorgfalt geboten. In C, C++, Java, C#, JavaScript, Go, Rust, Swift und PHP hat der Rest das Vorzeichen der Zahl, daher ist -3 % 2 -1 und nicht 1. Bei einer geraden Zahl ist der Rest unabhängig von ihrem Vorzeichen 0, daher ist x % 2 == 0 immer korrekt, während ein ungerader Test in der Form x % 2 == 1 jede negative ungerade Zahl übersieht. Für [-4, -3, 0, 7] sind die Reste 0, -1, 0 und 1, sodass der Zähler am Ende 2 beträgt.

Auch Null wird mitgezählt: 0 % 2 ist 0, also ist 0 gerade.

Algorithmus

Setze count auf 0.
Durchlaufe jeden Wert x in nums.
Wenn x % 2 == 0, addiere 1 zu count.
Gib nach der Schleife count zurück.

def countEvens(nums):
    count = 0
    for x in nums:
        if x % 2 == 0:  # 0 also works for negatives, where the remainder can be -1
            count += 1
    return count

Stolperfallen und Grenzfälle

Die Fehler hier sind auf negative Zahlen und auf null zurückzuführen.

Die Anzahl der ungeraden Werte mit x % 2 == 1 zählen und von der Länge abziehen. In C-ähnlichen Sprachen ist -3 % 2 gleich -1, daher wird -3 nie als ungerade gezählt und stattdessen als gerade.
0 weder als gerade noch als ungerade behandeln. 0 = 2 × 0, also ist die Zahl gerade, und [0] gibt 1 zurück.
Den Bit-Test als x & 1 == 0 schreiben. In C, C++ und JavaScript bindet == stärker als &, bedeutet also x & (1 == 0), was immer 0 ergibt und nichts zählt. Schreibe (x & 1) == 0.
Die Schleife in einer Sprache mit 0-basierter Indizierung beim Index 1 beginnen lassen, wodurch der erste Wert übersprungen wird, oder in Lua und R bei 0 beginnen lassen, obwohl sich der erste Wert dort am Index 1 befindet.

Häufige Fragen4

Wie prüft man im Code, ob eine Zahl gerade ist?

Prüfe, ob der Rest nach der Division durch 2 null ist: x % 2 == 0. Das funktioniert in jeder gängigen Programmiersprache für positive Zahlen, negative Zahlen und null. Eine weitere Möglichkeit ist, das niedrigste Bit mit (x & 1) == 0 zu prüfen, da gerade Zahlen auf ein 0-Bit enden.

Ist null eine gerade Zahl?

Ja. Null geteilt durch 2 ist 0 ohne Rest und erfüllt daher die Definition einer geraden Zahl. Sie liegt außerdem zwischen den ungeraden Zahlen -1 und 1, genau dort, wo eine gerade Zahl hingehört.

Warum schlägt x % 2 == 1 bei negativen Zahlen fehl?

In C, C++, Java, C#, JavaScript, Go, Rust, Swift und PHP hat der Rest das Vorzeichen der Zahl, die geteilt wird, daher ist -3 % 2 gleich -1. Python, Ruby, Dart, Lua und R geben stattdessen 1 zurück. Die Prüfung von x % 2 != 0 auf ungerade und x % 2 == 0 auf gerade Zahlen liefert in allen diesen Sprachen dasselbe Ergebnis.

Wie hoch ist die Zeitkomplexität beim Zählen gerader Zahlen in einem Array?

Ein Durchlauf mit einem Zähler benötigt O(n) Zeit und O(1) zusätzlichen Speicherplatz. Jeder Wert muss überprüft werden, daher ist keine Methode schneller als O(n). Zuerst eine gefilterte Liste zu erstellen, ergibt dieselbe Anzahl, benötigt aber O(n) zusätzlichen Speicher.

Python

def countEvens(nums):
    # Schreibe hier deinen Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [3, 8, 12, 5, 6]

Erwartet