CODEWITHSUNDEEP
javascriptarraysalgorithm
larry8989
larry8989

Reputation: 339

Minimum change that cannot be created

The following code finds the minimum change that cannot be created from a list of coins.

For example, the minimum change that cannot be created from [1,2,5] is 4.

This works for the following array [5,7,1,1,2,3,22] which is 20.

However, I cannot figure out how to account for the array [1,1,1,1,1].

The minimum change I cannot create is 6.

How can I account for the array of ones? Thank you.

function nonConstructibleChange(coins) {
      
  coins.sort( (a,b) => a - b);
    
  let currentChangeCreated = 0;

  for (let i = 0; i < coins.length; i++) {

    if (coins[i] > currentChangeCreated + 1) {
      return currentChangeCreated + 1;
    }

    currentChangeCreated += coins[i];

  }
        
  return currentChangeCreated;
}

Upvotes: 0

Views: 48

Answers (2)

jarmod
jarmod

Reputation: 78733

If you iterate over all the coins and haven't yet found the result, then the minimum change you cannot create must be the total of all the coins + 1.

Change the final return statement to:

return currentChangeCreated + 1

By the way, your successful test cases all complete and return before exhausting the list of coins, hence that final return statement is not executed in those cases.

Upvotes: 2

Dmitry Y.
Dmitry Y.

Reputation: 53

As for [1, 1, 1, 1, 1], you can create any change between 1 and 5, so 6 it's just the closest you can't create after 5.

Upvotes: 0

Related Questions