Problema
Considera los enteros positivos estrictamente menores que el límite. Incluye un valor si es divisible por al menos un factor distinto de cero. Cuenta cada valor incluido solo una vez, incluso si varios factores lo dividen. Ignora los factores que sean cero. Los factores [3, 5] corresponden al conocido ejercicio de múltiplos de 3 o 5.
Implementa sum_of_multiples(limit, factors).
Entrada
limit: El límite superior exclusivo.
factors: Los factores cuyos múltiplos son elegibles.
Salida
Devuelve la suma de los enteros positivos distintos que cumplen la condición.
Restricciones
0 ≤ limit ≤ 100,000. Puede haber entre 0 y 20 factores, cada uno entre 0 y 100,000. Se permiten factores duplicados.
Ejemplos
Entrada:
limit = 12
factors = [3, 5]
Salida esperada:
expected = 33Entrada:
long long limit = 12;
std::vector<long long> factors = {3, 5};
Salida esperada:
long long expected = 33;Entrada:
long limit = 12;
long[] factors = new long[] {3, 5};
Salida esperada:
long expected = 33;Explicación
Los valores incluidos son 3, 5, 6, 9 y 10. Su suma es 33.
Entrada:
limit = 10
factors = [2, 4]
Salida esperada:
expected = 20Entrada:
long long limit = 10;
std::vector<long long> factors = {2, 4};
Salida esperada:
long long expected = 20;Entrada:
long limit = 10;
long[] factors = new long[] {2, 4};
Salida esperada:
long expected = 20;Explicación
Incluye 2, 4, 6 y 8. Los valores 4 y 8 se cuentan solo una vez aunque coincidan con ambos factores.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Solo los valores divisibles por al menos un factor útil deben contribuir una sola vez.
Pista 2
Usa inclusion-exclusion para combinar los múltiplos de factores solapados sin doble conteo.
Pista 3
Ignora factores cero y duplicados antes de hacer cualquier cálculo.
Complejidad esperada
tiempo O(2^m), espacio extra O(1)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.