Problema
Puedes seleccionar cualquier subconjunto de las monedas proporcionadas. Cada moneda individual puede usarse como máximo una vez, incluso si hay varias monedas con el mismo valor. Encuentra el menor entero positivo que no pueda obtenerse con ninguna selección.
Implementa missing_coin_sum(coins).
Entrada
coins: Los valores de las monedas disponibles; los duplicados representan monedas distintas.
Salida
Devuelve la menor cantidad positiva imposible de obtener.
Restricciones
1 ≤ número de monedas ≤ 200,000. Cada valor está entre 1 y 1,000,000,000.
Ejemplos
Entrada:
coins = [1, 1, 4]
Salida esperada:
expected = 3Entrada:
std::vector<long long> coins = {1, 1, 4};
Salida esperada:
long long expected = 3;Entrada:
long[] coins = new long[] {1, 1, 4};
Salida esperada:
long expected = 3;Explicación
Las cantidades 1 y 2 se pueden formar usando las monedas de valor uno. No existe ningún subconjunto disponible que sume 3.
Entrada:
coins = [2, 3]
Salida esperada:
expected = 1Entrada:
std::vector<long long> coins = {2, 3};
Salida esperada:
long long expected = 1;Entrada:
long[] coins = new long[] {2, 3};
Salida esperada:
long expected = 1;Explicación
No hay forma de obtener 1 porque todas las monedas valen al menos 2.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Ordena las monedas y construye la menor suma alcanzable de menor a mayor.
Pista 2
Si la siguiente moneda es mayor que la primera suma no alcanzable, esa suma ya nunca podrá formarse.
Pista 3
Los duplicados solo ayudan si amplían el rango alcanzable actual sin huecos.
Complejidad esperada
O(n log n) time, O(1) extra space, excluding sorting implementation details
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.