Count Even Numbers

Q: Comment vérifier dans le code si un nombre est pair ?

Vérifiez si le reste après division par 2 est nul : x % 2 == 0 . Cela fonctionne pour les nombres positifs, les nombres négatifs et zéro dans tous les langages courants. Une autre méthode consiste à vérifier le bit de poids faible avec (x & 1) == 0 , car les nombres pairs se terminent par un bit 0 .

Q: Est-ce que zéro est un nombre pair ?

Oui. Zéro divisé par 2 donne 0 sans reste, ce qui correspond à la définition d’un nombre pair. Il se trouve également entre les nombres impairs -1 et 1 , exactement là où se trouve un nombre pair.

Q: Quelle est la complexité temporelle du comptage des nombres pairs dans un tableau ?

Un seul parcours avec un compteur prend un temps de O(n) et utilise un espace supplémentaire de O(1) . Chaque valeur doit être vérifiée, donc aucune méthode n’est plus rapide que O(n) . Construire d’abord une liste filtrée donne le même décompte, mais utilise une mémoire supplémentaire de O(n) .

DébutantTableaux et chaînes Maths et simulation

+10

Vous recevez une liste non vide d’entiers nums. Retournez le nombre de ses valeurs qui sont paires. Un nombre est pair lorsque sa division par 2 ne laisse aucun reste, ce qui inclut 0 et les nombres négatifs tels que -4.

Fonction

countEvens(nums: integer-array) → integer

numsinteger-array: la liste d’entiers à vérifier
Renvoieinteger: le nombre de valeurs paires dans nums

Contraintes

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

Exemples

Entrée: nums = [3, 8, 12, 5, 6]
Sortie: 3
Explication: 8, 12 et 6 sont divisibles par 2 sans laisser de reste, tandis que 3 et 5 laissent un reste. Cela fait 3 nombres pairs.

Entrée: nums = [-4, -3, 0, 7]
Sortie: 2
Explication: -4 = 2 × (-2) et 0 = 2 × 0, donc les deux sont pairs. -3 et 7 sont impairs, et le nombre est 2.

Entrée: nums = [1, 9, 15]
Sortie: 0
Explication: 1, 9 et 15 sont tous impairs, donc aucune valeur n'est comptabilisée et la réponse est 0.

+12 tests cachés à la soumission

Pour aller plus loin

On vous pose de nombreuses questions de la forme : combien de valeurs paires se trouvent entre l’indice l et l’indice r ? Après un seul parcours de nums, pouvez-vous répondre à chaque question en temps O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La boucle tient sur une ligne ; c’est le test de parité qui fait échouer les solutions. Dans de nombreux langages, le reste d’un nombre négatif est négatif, donc -3 % 2 vaut -1. Tester x % 2 == 0 est correct quel que soit le signe, dans tous les langages, et un compteur incrémental ne nécessite pas de mémoire supplémentaire.

Récupérez les valeurs paires, puis comptez-les

Intuition

Divise la tâche en deux étapes : repère les valeurs paires, puis compte celles que tu as repérées. Une valeur x est paire lorsque x % 2 == 0. La plupart des langages ont une fonction de filtrage qui construit la nouvelle liste en une seule ligne, et sa longueur donne la réponse. Pour [3, 8, 12, 5, 6], la liste filtrée est [8, 12, 6], donc la réponse est 3.

C’est correct et facile à lire, mais la nouvelle liste nécessite une mémoire de O(n), jusqu’à 5000 valeurs ici, uniquement pour lire sa longueur une fois. Les valeurs elles-mêmes ne sont jamais réutilisées.

Algorithme

Créez une nouvelle liste contenant chaque x de nums pour lequel x % 2 == 0.
Renvoyez la longueur de cette liste.

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

Compter avec un compteur incrémental

Intuition

Utilisez un compteur au lieu d’une liste. Initialisez-le à 0, examinez chaque valeur une seule fois et ajoutez 1 lorsque la valeur est paire. Chaque valeur est vérifiée exactement une fois, le décompte est donc exact, et la seule mémoire utilisée est celle d’un entier.

Le test mérite une attention particulière. En C, C++, Java, C#, JavaScript, Go, Rust, Swift et PHP, le reste a le signe du nombre : ainsi, -3 % 2 vaut -1, et non 1. Un nombre pair donne un reste de 0, quel que soit son signe : x % 2 == 0 est donc toujours correct, tandis qu’un test d’impair écrit comme x % 2 == 1 ne détecte aucun nombre impair négatif. Pour [-4, -3, 0, 7], les restes sont 0, -1, 0 et 1 ; le compteur termine donc à 2.

Zéro compte aussi : 0 % 2 vaut 0, donc 0 est pair.

Algorithme

Définis count à 0.
Parcours chaque valeur x dans nums.
Si x % 2 == 0, ajoute 1 à count.
Après la boucle, renvoie count.

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

Pièges et cas limites

Les bogues viennent ici des nombres négatifs et de zéro.

Compter les valeurs impaires avec x % 2 == 1 et soustraire ce nombre de la longueur. Dans les langages de type C, -3 % 2 vaut -1, donc -3 n’est jamais compté comme impair et finit par être compté comme pair.
Considérer que 0 n’est ni pair ni impair. 0 = 2 × 0, donc il est pair, et [0] renvoie 1.
Écrire le test de bit sous la forme x & 1 == 0. En C, C++ et JavaScript, == a une priorité supérieure à &, donc cela signifie x & (1 == 0), ce qui vaut toujours 0 et ne compte rien. Écrivez (x & 1) == 0.
Commencer la boucle à l’index 1 dans un langage indexé à partir de 0, ce qui ignore la première valeur, ou à 0 en Lua et R, où la première valeur se trouve à l’index 1.

Questions fréquentes4

Comment vérifier dans le code si un nombre est pair ?

Vérifiez si le reste après division par 2 est nul : x % 2 == 0. Cela fonctionne pour les nombres positifs, les nombres négatifs et zéro dans tous les langages courants. Une autre méthode consiste à vérifier le bit de poids faible avec (x & 1) == 0, car les nombres pairs se terminent par un bit 0.

Est-ce que zéro est un nombre pair ?

Oui. Zéro divisé par 2 donne 0 sans reste, ce qui correspond à la définition d’un nombre pair. Il se trouve également entre les nombres impairs -1 et 1, exactement là où se trouve un nombre pair.

Pourquoi x % 2 == 1 échoue-t-il pour les nombres négatifs ?

En C, C++, Java, C#, JavaScript, Go, Rust, Swift et PHP, le reste prend le signe du nombre divisé, donc -3 % 2 vaut -1. Python, Ruby, Dart, Lua et R renvoient plutôt 1. Tester x % 2 != 0 pour savoir si un nombre est impair et x % 2 == 0 pour savoir s’il est pair donne la même réponse dans tous ces langages.

Quelle est la complexité temporelle du comptage des nombres pairs dans un tableau ?

Un seul parcours avec un compteur prend un temps de O(n) et utilise un espace supplémentaire de O(1). Chaque valeur doit être vérifiée, donc aucune méthode n’est plus rapide que O(n). Construire d’abord une liste filtrée donne le même décompte, mais utilise une mémoire supplémentaire de O(n).

Python

def countEvens(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu