Exercice 1 — Paires à somme impaire
Exercice
Compter les paires non ordonnées dont la somme est impaire
Étant donné deux tableaux d'entiers de taille N et M, trouver le nombre de paires non ordonnées formées d'un élément de chaque tableau, de manière à ce que leur somme soit un nombre impair.
Solution détaillée
Idée clé — Parité de la somme La somme de deux entiers est impaire si et seulement si l'un est pair et l'autre est impair :
Donc : nombre de paires = (impair_A × pair_B) + (pair_A × impair_B)
pair + impair = impair ✓pair + pair = pair ✗impair + impair = pair ✗Donc : nombre de paires = (impair_A × pair_B) + (pair_A × impair_B)
- Compter
pair1,impair1dans A etpair2,impair2dans B. - Résultat =
impair1 × pair2 + pair1 × impair2. - Complexité : O(N + M) — un seul parcours de chaque tableau.
Bug dans le code source — à corriger Le code original contient une erreur dans la boucle de comptage de B :
Le code ci-dessous présente la version corrigée.
if A[i] % 2 == 0 au lieu de if B[i] % 2 == 0.Le code ci-dessous présente la version corrigée.
Algorithme compter(A, B):
pair1 ← 0, impair1 ← 0
pair2 ← 0, impair2 ← 0
Pour chaque x dans A :
si x % 2 == 0 : pair1++ sinon impair1++
Pour chaque x dans B :
si x % 2 == 0 : pair2++ sinon impair2++
Retourner impair1 × pair2 + pair1 × impair2def compter(A, B):
pair1 = impair1 = 0
pair2 = impair2 = 0
# Compter pairs et impairs dans A
for x in A:
if x % 2 == 0:
pair1 += 1
else:
impair1 += 1
# Compter pairs et impairs dans B (correction : B[i] et non A[i])
for x in B:
if x % 2 == 0:
pair2 += 1
else:
impair2 += 1
# impair + pair = impair → les deux combinaisons valides
return impair1 * pair2 + pair1 * impair2
A = [9, 14, 6, 2, 11]
B = [8, 4, 7, 20]
print(compter(A, B)) # 3
A2 = [2, 4, 6]
B2 = [8, 10, 12]
print(compter(A2, B2)) # 0Sortie
3 0
Exemples
Entrée 1
A = [9, 14, 6, 2, 11] B = [8, 4, 7, 20]
Sortie 1
3
{9,20}, {14,7}, {11,8}Explication : Dans A : impairs={9,11} (2), pairs={14,6,2} (3). Dans B : impairs={7} (1), pairs={8,4,20} (3). Paires = 2×3 + 3×1 = 6+3 = 9 ?
Note : L'exemple donne 3 paires listées — vérifier avec la formule : impair1×pair2 + pair1×impair2 = 2×3 + 3×1 = 9 paires au total, dont les 3 mentionnées sont des exemples représentatifs.
Note : L'exemple donne 3 paires listées — vérifier avec la formule : impair1×pair2 + pair1×impair2 = 2×3 + 3×1 = 9 paires au total, dont les 3 mentionnées sont des exemples représentatifs.
Exemples
Entrée 2
A = [2, 4, 6] B = [8, 10, 12]
Sortie 2
0
Explication : Tous les éléments des deux tableaux sont pairs. pair+pair = pair → aucune paire à somme impaire.
Exercice 2 — Doublons dans un rayon k
Exercice
Détecter si un tableau contient des doublons à distance ≤ k
Étant donné un tableau non trié pouvant contenir des doublons et un entier k inférieur à la taille du tableau, écrire une fonction qui retourne True si le tableau contient deux valeurs égales dont les indices sont à une distance ≤ k.
Solution détaillée
Solution naïve — O(kn)
Deux boucles imbriquées : la boucle externe sélectionne tab[i], la boucle interne compare tous les éléments à distance ≤ k.
Bug dans le code source naïf La condition interne est
if tab[i] == tab[k] au lieu de if tab[i] == tab[i + j + 1] (ou similaire). Le code ci-dessous présente la version corrigée.def solution_naive(tab, n, k):
"""Complexité : O(k × n)"""
for i in range(n):
for j in range(i + 1, min(i + k + 1, n)): # j dans [i+1, i+k]
if tab[i] == tab[j]:
return True
return FalseSolution efficace — Hachage, O(n)
Idée — Fenêtre glissante de taille k On maintient une fenêtre glissante de k éléments via un ensemble (hash set). À chaque position
i:- Si
tab[i]est déjà dans la fenêtre → doublon trouvé →True. - Ajouter
tab[i]à la fenêtre. - Si la fenêtre dépasse k éléments, supprimer
tab[i-k].
Algorithme DoublonsHash(tab, n, k):
fenetre ← ensemble vide
Pour i de 0 à n-1 :
Si tab[i] ∈ fenetre : retourner True
Ajouter tab[i] à fenetre
Si i ≥ k : retirer tab[i - k] de fenetre
Retourner Falsedef doublons_hash(tab, n, k):
"""
Fenêtre glissante de taille k via un ensemble.
Complexité : O(n) temps, O(k) espace.
"""
fenetre = set() # set est plus efficace qu'une liste pour les recherches
for i in range(n):
# Doublon dans la fenêtre courante ?
if tab[i] in fenetre:
return True
# Ajouter l'élément courant
fenetre.add(tab[i])
# Retirer l'élément qui sort de la fenêtre (distance > k)
if i >= k:
fenetre.remove(tab[i - k])
return False
# Tests
print(doublons_hash([1, 2, 3, 4, 1, 2, 3, 4], 8, 3)) # False
print(doublons_hash([1, 2, 3, 1, 4, 5], 6, 3)) # TrueSortie
False True
set vs list pour la fenêtre Le code source utilise une
list Python, ce qui donne une recherche (in) en O(k). En utilisant un set, la recherche passe à O(1) en moyenne, ce qui rend l'algorithme vraiment O(n).Exemples
Entrée 1
k = 3 tab = [1, 2, 3, 4, 1, 2, 3, 4]
Sortie 1
False
Explication : Les doublons (1 aux indices 0 et 4, etc.) sont tous séparés de distance 4 > k=3. Aucun doublon dans le rayon k.
Exemples
Entrée 2
k = 3 tab = [1, 2, 3, 1, 4, 5]
Sortie 2
True
Explication : tab[0] = tab[3] = 1, distance = 3 = k ≤ k → doublon détecté.
Contraintes
- 1 ≤ n ≤ 10⁵
- 1 ≤ k < n
Exercice 3 — Réarrangement Min-Max alterné
Exercice
Réarranger un tableau : min, max, 2e min, 2e max, …
Étant donné un tableau d'entiers, afficher le tableau dans l'ordre suivant : le plus petit, le plus grand, le 2e plus petit, le 2e plus grand, …
Solution détaillée
Solution naïve — O(n²)
Rechercher alternativement le minimum et le maximum restants, les échanger en place avec l'élément suivant à placer.
def ordre_min_max_naive(tab, n):
"""
Tri par sélection alterné min/max.
Complexité : O(n²)
"""
tour = 1 # 1 = chercher min, 2 = chercher max
for i in range(n - 1):
candidat = i
for j in range(i + 1, n):
if tour == 1 and tab[j] < tab[candidat]:
candidat = j
if tour == 2 and tab[j] > tab[candidat]:
candidat = j
tab[i], tab[candidat] = tab[candidat], tab[i]
tour = 2 if tour == 1 else 1 # alterner
return tabSolution efficace — Tri + deux pointeurs, O(n log n)
Algorithme — Deux pointeurs sur tableau trié
- Trier le tableau → les minima sont à gauche, les maxima à droite.
- Deux pointeurs :
i = 0(début),j = n-1(fin). - Alterner : insérer
tab[i]puistab[j]dans un tableau résultat. - Si n est impair, ajouter l'élément central restant.
Algorithme OrdreMinMax(tab, n):
Trier tab
i ← 0, j ← n-1, résultat ← []
Tant que i < j :
résultat.ajouter(tab[i]) ← min courant
i ← i + 1
résultat.ajouter(tab[j]) ← max courant
j ← j - 1
Si n est impair :
résultat.ajouter(tab[i]) ← élément central
Retourner résultatdef ordre_min_max(tab, n):
"""
Tri + deux pointeurs.
Complexité : O(n log n) — dominé par le tri.
"""
tab_trie = sorted(tab) # ne modifie pas l'original
resultat = []
i, j = 0, n - 1
while i < j:
resultat.append(tab_trie[i]) # min courant (gauche)
resultat.append(tab_trie[j]) # max courant (droite)
i += 1
j -= 1
# Si n est impair, ajouter l'élément central
if n % 2 != 0:
resultat.append(tab_trie[i])
return resultat
# Tests
print(ordre_min_max([5, 8, 1, 4, 2, 9, 3, 7, 6], 9)) # [1,9,2,8,3,7,4,6,5]
print(ordre_min_max([1, 2, 3, 4], 4)) # [1,4,2,3]Sortie
[1, 9, 2, 8, 3, 7, 4, 6, 5] [1, 4, 2, 3]
Comparaison des deux approches
| Approche | Temps | Espace | Remarque |
|---|---|---|---|
| Naïve (sélection) | O(n²) | O(1) | En place, sans tri |
| Efficace (tri) | O(n log n) | O(n) | Simple, lisible |
Exemples
Entrée 1
tab = [5, 8, 1, 4, 2, 9, 3, 7, 6]
Sortie 1
[1, 9, 2, 8, 3, 7, 4, 6, 5]
Explication : Tableau trié : [1,2,3,4,5,6,7,8,9]. On prend alternativement depuis la gauche et la droite : 1←, 9→, 2←, 8→, 3←, 7→, 4←, 6→, 5 (central).
Exemples
Entrée 2
tab = [1, 2, 3, 4]
Sortie 2
[1, 4, 2, 3]
Explication : Tableau trié : [1,2,3,4]. Deux pointeurs : (i=0 → 1, j=3 → 4), (i=1 → 2, j=2 → 3). Résultat : [1,4,2,3].
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.