Problème
Considérez les entiers positifs strictement inférieurs à la limite. Incluez une valeur si elle est divisible par au moins un facteur non nul. Comptez chaque valeur incluse une seule fois, même si plusieurs facteurs la divisent. Ignorez les facteurs nuls. Les facteurs [3, 5] correspondent au classique exercice des multiples de 3 ou 5.
Implémentez sum_of_multiples(limit, factors).
Entrée
limit : La borne supérieure exclusive.
factors : Les facteurs dont les multiples sont éligibles.
Sortie
Retournez la somme des entiers positifs distincts éligibles.
Contraintes
0 ≤ limit ≤ 100 000. Il peut y avoir de 0 à 20 facteurs, chacun compris entre 0 et 100 000. Les facteurs dupliqués sont autorisés.
Exemples
Entrée :
limit = 12
factors = [3, 5]
Sortie attendue :
expected = 33Entrée :
long long limit = 12;
std::vector<long long> factors = {3, 5};
Sortie attendue :
long long expected = 33;Entrée :
long limit = 12;
long[] factors = new long[] {3, 5};
Sortie attendue :
long expected = 33;Explication
Les valeurs incluses sont 3, 5, 6, 9 et 10. Leur somme est 33.
Entrée :
limit = 10
factors = [2, 4]
Sortie attendue :
expected = 20Entrée :
long long limit = 10;
std::vector<long long> factors = {2, 4};
Sortie attendue :
long long expected = 20;Entrée :
long limit = 10;
long[] factors = new long[] {2, 4};
Sortie attendue :
long expected = 20;Explication
Inclure 2, 4, 6 et 8. Les valeurs 4 et 8 ne sont comptées qu'une seule fois même si elles correspondent aux deux facteurs.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Seules les valeurs divisibles par au moins un facteur utilisable doivent compter une fois.
Indice 2
Utilise le principe d’inclusion-exclusion pour combiner les multiples qui se recouvrent sans double compter.
Indice 3
Ignore les facteurs nuls et les doublons avant tout calcul.
Complexité attendue
temps O(2^m), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.