Résoudre LeetCode 3116 avec recherche binaire et inclusion-exclusion
Une boucle en force brute sur des milliards de multiples est souvent la première idée face à LeetCode 3116 — jusqu’à ce qu’on réalise que k peut atteindre 2×10⁹ et que le temps presse. Le vrai défi n’est pas l’énoncé, mais l’association élégante entre une recherche binaire sur la réponse et un décompte par inclusion-exclusion, transformant un problème à 26 % de réussite en un casse-tête maîtrisable.
Recherche binaire sur la réponse
Plutôt que de générer chaque candidat jusqu’à k, l’astuce consiste à rechercher binairement la plus petite valeur X telle que le nombre de montants valides ≤ X soit au moins k. L’espace de recherche est borné par k multiplié par la valeur maximale des pièces, ce qui limite la profondeur du logarithme. Le vrai goulot d’étranglement n’est pas la recherche binaire elle-même, mais le comptage des multiples de toute sous-ensemble non vide de pièces, sans double-compter les chevauchements.
Inclusion-exclusion via masque binaire
La fonction count(X) exploite l’inclusion-exclusion sur l’ensemble des pièces via une itération sur masques binaires. Pour chaque sous-ensemble non vide, on calcule le plus petit commun multiple (PPCM) à l’aide du PGCD, puis on décide d’ajouter ou de soustraire ses multiples selon la parité de la taille du sous-ensemble. Si le PPCM dépasse X, on peut interrompre prématurément, élaguant ainsi l’arbre de recherche. La complexité devient O(n · 2ⁿ · log(k·M)), suffisamment légère pour s’exécuter en quelques secondes même aux limites supérieures.
Pourquoi c’est important
LeetCode 3116 n’est pas qu’un simple problème de comptage ; c’est un microcosme où la pensée algorithmique triomphe de la force brute. En identifiant la monotonie et en appliquant l’inclusion-exclusion avec l’efficacité des masques binaires, les programmeurs contournent une énumération impossible. La leçon dépasse les concours : toute situation exigeant de compter des combinaisons valides sous contraintes peut tirer profit de cette approche diviser-pour-régner.
Source : DEV Community. Synthèse éditoriale assistée par IA — TechnoExpress.