Problème
Vous pouvez sélectionner n'importe quel sous-ensemble des pièces fournies. Chaque pièce individuelle ne peut être utilisée qu'une seule fois, même si plusieurs pièces ont la même valeur. Trouvez le plus petit entier positif qu'aucune sélection ne peut produire.
Implémentez missing_coin_sum(coins).
Entrée
coins : Les valeurs des pièces disponibles ; les doublons représentent des pièces distinctes.
Sortie
Retournez le plus petit montant positif impossible à obtenir.
Contraintes
1 ≤ nombre de pièces ≤ 200 000. Chaque valeur est comprise entre 1 et 1 000 000 000.
Exemples
Entrée :
coins = [1, 1, 4]
Sortie attendue :
expected = 3Entrée :
std::vector<long long> coins = {1, 1, 4};
Sortie attendue :
long long expected = 3;Entrée :
long[] coins = new long[] {1, 1, 4};
Sortie attendue :
long expected = 3;Explication
Les montants 1 et 2 sont réalisables avec les pièces de valeur 1. Aucun sous-ensemble disponible ne permet d'obtenir 3.
Entrée :
coins = [2, 3]
Sortie attendue :
expected = 1Entrée :
std::vector<long long> coins = {2, 3};
Sortie attendue :
long long expected = 1;Entrée :
long[] coins = new long[] {2, 3};
Sortie attendue :
long expected = 1;Explication
Il est impossible d'obtenir 1 car chaque pièce vaut au moins 2.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Trie les pièces et construis la plus petite somme atteignable à partir des plus petites.
Indice 2
Si la pièce suivante est plus grande que la première somme impossible à atteindre, cette somme ne pourra jamais être formée.
Indice 3
Les doublons aident seulement s’ils étendent la plage actuellement atteignable sans créer de trou.
Complexité attendue
O(n log n) time, O(1) extra space, excluding sorting implementation details
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.