Estoy trabajando en los desafíos de codificación de algoexpert.io y tengo problemas para entender la solución sugerida a una de las preguntas titulada Cambio no construible
Aquí está la pregunta de desafío:
Dada una matriz de enteros positivos que representan los valores de las monedas que posee, escriba una función que devuelva la cantidad mínima de cambio (la suma mínima de dinero) que no puede crear. Las monedas dadas pueden tener cualquier valor entero positivo y no son necesariamente únicas (es decir, puede tener varias monedas del mismo valor).
Por ejemplo, si le dan monedas = [1, 2, 5], la cantidad mínima de cambio que no puede crear es 4. Si no recibe monedas, la cantidad mínima de cambio que no puede crear es 1.
// O(nlogn) time, O(n) size. function nonConstructibleChange(coins) { coins = coins.sort((a, b) => a - b); // O(nlogn) time operation let change = 0; for (coin of coins) { if (coin > change + 1) return change + 1; change += coin; } return change + 1; }Mi problema
No estoy completamente seguro de cómo el autor de la solución llegó a la intuición de que
if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.Puedo ver cómo rastrea y, de hecho, el algoritmo pasa todas las pruebas, pero me gustaría saber más sobre un proceso que podría usar para diseñar esta regla.
¡Gracias por tomarse el tiempo de leer la pregunta!
Me las arreglé para abordarlo sin la cosa + 1, rastreando el cambio mínimo imposible actual, así:
function nonConstructibleChange(coins) { let currentMinImpossibleChange = 1; const sortedCoins = coins.sort((a,b) => ab) for(let i = 0; i < sortedCoins.length ; i += 1) { if(currentMinImpossibleChange < sortedCoins[i]) return currentMinImpossibleChange currentMinImpossibleChange += sortedCoins[i]; } return currentMinImpossibleChange; }Después de un rato pensando en eso, pensé que era un problema de probabilidad. Quiero decir, ¿cuántos cambios son posibles con N monedas?
Esto significa que debo combinar todas las posibilidades. Por ejemplo, dadas coins = [1, 5, 9] , ¿cuál es la cantidad mínima de cambio que se puede hacer?
1 -> 1, 1+5, 1+9, 1+5+9. 5 -> 5, 5+9. 9 -> 9. resultando en possible changes = [1, 6, 10, 15, 14, 9] .
Entonces, la cantidad mínima de cambio que se puede crear usando estas 3 monedas [1, 5, 9] debería ser 2 .
Por cierto, si ese fuera el caso, este es un O(2^n) time porque por cada nueva moneda (cada nueva posibilidad) el número de cálculos se duplica.
Desafortunadamente, ese no es el caso...
Cuando se ordenan los enteros, siempre podemos rastrear el valor construible más alto haciendo una suma acumulativa de los enteros ordenados.
Por ejemplo, coins = [1, 2, 5] ==> 1,2,3,5,6,7
En cualquier momento, si el siguiente entero es mayor que max construible + 1, entonces no hay forma de construir max construible + 1.
[1] mc=1 ---> 2 [1, 2] mc=3 ---> 4 [1, 2, 5] mc=7 ---> 8 Si el entero actual es mayor que mc + 1 , el cambio más pequeño imposible es igual a mc + 1 .
Entonces, en este caso, para [1, 2, 5] el valor más pequeño es 4.
Se puede hacer así (estoy usando go)
func NonConstructibleChange(array []int) int { sort.Ints(array) ncc :=1 for i:=0; i< len(array) && array[i]<=ncc; i++{ ncc +=array[i] } return ncc }Este también me tomó un tiempo, pero así fue como lo entendí:
Suponga que ha demostrado que puede ganar de 1 a 8 centavos.
Pasas a la siguiente iteración y quieres saber si puedes hacer 9 centavos. Entonces iteras a la siguiente moneda nueva en la lista ordenada.
si moneda nueva < 9:
si moneda nueva == 9:
si nuevaCoin > 9:
Y de ahí viene el cambio + 1. (tu cambio de variable = 8)
if the current coin is greater than `change + 1`, the smallest impossible change is equal to `change + 1`.