Accueil › Coding & algorithmique › Deux montants pour atteindre la cible
Deux montants pour atteindre la cible
Exercice de la série « Tableaux et parcours »debutant
Le problème. Un catalogue de prix déjà triés par ordre croissant. On veut deux articles distincts dont la somme fait exactement le budget.
Écrivez deuxPrix(prix, budget) qui renvoie les positions des deux
articles, dans l'ordre croissant, ou null si aucune paire ne convient.
Quand plusieurs paires conviennent, renvoyez celle dont la première
position est la plus petite.
| Appel | Résultat attendu |
|---|---|
deuxPrix([1, 2, 4, 7], 8) |
[0, 3] |
deuxPrix([1, 2, 4, 7], 6) |
[1, 2] |
deuxPrix([1, 2, 3], 7) |
null |
deuxPrix([3, 3], 6) |
[0, 1] |
deuxPrix([], 5) |
null |
Ce qu'on attend. Le tableau est trié : c'est le signal des deux pointeurs convergents, et une réponse en O(n) sans mémoire supplémentaire.
Le piège. Quand la somme est trop grande, lequel des deux indices faut-il bouger ? Se tromper donne un code qui réussit les cas faciles et rate les autres.
Cas de test
[[1,2,4,7],8][[1,2,4,7],6][[1,2,3],7][[3,3],6][[],5][[5],5]
Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.