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 égal à zéro : x % 2 == 0 . Cela fonctionne pour les nombres positifs, les nombres négatifs et zéro, même dans les langages où -3 % 2 vaut -1 . Vous pouvez aussi vérifier le bit de poids faible avec (x & 1) == 0 .

Q: Le zéro est-il 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 , où se situe un nombre pair.

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

Un seul passage avec un compteur prend un temps de O(n) et 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) .

DébutantTableaux et chaînes Maths et simulation

+10

Étant donné une liste non vide d’entiers nums, renvoie 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 des 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 reste ; 3 et 5 ne le sont pas. La réponse est 3.

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 la réponse est 0.

Pour aller plus loin

On vous pose souvent la question suivante : 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 à chacune en O(1) ?

Indices

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

0 sur 3 ouverts

Solution

Vérifie chaque valeur une fois et compte celles qui donnent un reste de 0 lorsqu’elles sont divisées par 2. Comparer le reste à 0, plutôt que de vérifier si le reste vaut 1 pour détecter les nombres impairs, fonctionne aussi correctement avec les nombres négatifs.

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

Intuition

Sélectionnez les valeurs paires avec un filtre, puis renvoyez la longueur du résultat. Pour [3, 8, 12, 5, 6], la liste filtrée est [8, 12, 6], donc la réponse est 3.

La complexité temporelle est de O(n), mais la nouvelle liste consomme O(n) de mémoire, jusqu’à 5000 valeurs, uniquement pour lire sa longueur une fois.

Algorithme

Crée une nouvelle liste contenant chaque x de nums tel que x % 2 == 0.
Renvoie 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 évolutif

Intuition

Gardez un compteur au lieu d’une liste, et ajoutez 1 pour chaque valeur avec x % 2 == 0. Un nombre pair laisse un reste de 0 quel que soit son signe, donc le test est vrai pour -4 et 0 dans tous les langages. Un test pour les nombres impairs écrit x % 2 == 1 ne l’est pas : en C, Java, JavaScript et dans la plupart des langages de type C, le reste prend le signe du nombre, donc -3 % 2 vaut -1.

Un seul parcours et un seul entier : temps O(n), espace O(1).

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

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] renvoie 1 au lieu de 0.
Considérer que 0 n'est ni pair ni impair. 0 = 2 × 0, donc [0] renvoie 1.
Écrire le test binaire sous la forme x & 1 == 0. En C, C++ et JavaScript, == a une priorité plus élevée que &, donc l'expression signifie x & (1 == 0), ce qui vaut toujours 0 et ne compte rien. Écrire (x & 1) == 0.

Questions fréquentes3

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

Vérifiez si le reste après division par 2 est égal à zéro : x % 2 == 0. Cela fonctionne pour les nombres positifs, les nombres négatifs et zéro, même dans les langages où -3 % 2 vaut -1. Vous pouvez aussi vérifier le bit de poids faible avec (x & 1) == 0.

Le zéro est-il 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, où se situe un nombre pair.

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

Un seul passage avec un compteur prend un temps de O(n) et 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).

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu