Store subset of an array using repeated values as much as possible

Question

I'm stumbling into a problem that I've to treat a given value and check if this value is bigger than my array of values, if it is, combine the output using my array. I've already asked a similar question here : Store values in an array after treat the values from another array

Important NOTE, I want to repeat the subsets as much as possible. My solution only provides combination of subsets with different numbers.

For example.

My array always will be:

const ArrayPrimitive = [100,50,20,10];

And for example the given value in the input:

Entry: 30.00 Result: [20.00, 10.00]
Entry: 80.00 Result: [50.00, 20.00, 10.00]
Entry: 125.00 Result: throw NoteUnavailableException
Entry: -130.00 Result: throw InvalidArgumentException
Entry: NULL Result: [Empty Set]

Entry: 200 EXPECTED RESULT: [100.00, 100.00]* Here is where I'm stucked, i want to combine same values of the subset(my array
primitive) as much as possible before use smaller numbers.

In this case I need 2 values of 100 in my subset, and when I test this they functions throws me an error.

   const ArrayPrimitive = [100, 50, 20, 10]; // Assuming presorted     array(descending)

function findChange(m) {
  return ArrayPrimitive.reduce((mm, c) => {
    if (mm.rest >= c) {
      mm.change.push(c);
      mm.rest -= c
    }
    return mm
  }, {
    change: [],
    rest: m
  });
}

function findChangeOld(m) {
  var retval = {
      change: [],
      rest: m
    },
    i = ArrayPrimitive.length;

  for (var x = 0; x < i; x++) {
    if (retval.rest >= ArrayPrimitive[x]) {
      retval.change.push(ArrayPrimitive[x])
      retval.rest -= ArrayPrimitive[x];
    }
  }
  return retval;
}

function calcChange(v) {
  var c = findChangeOld(v);

  if (v < 0 || isNaN(v)) {
    console.log('${v}: throw InvalidArgumentException');
    return;
  }

  if (c.rest > 0)
    console.log('${v}: throw NoteUnavailableException');
  else
    console.log('${v}: ${c.change}');
}

calcChange(30);
calcChange(80);
calcChange(105);
calcChange(125);
calcChange(-130);
calcChange(null);

I hope I made myself clear.

Might have a solution for you: if you submit a number that is more than the total array sum (and in fact that point might help you see the solution) then do the check. E.g., your array sums up to 190. So any number > 190 (or rather, any number > arraysum + largestnum), you will look to see if combining the largest number in that array N times leaves you (modulus) with a leftover that can be fulfilled by the smaller numbers. If not, then you know you have to work with the smaller numbers. Yes? If it's not just the largest number, than you would recurse the mod result with each lesser number. — Tim Consolazio, Jan 19 '17 at 14:25
Sounds like the standard [change-making problem](https://en.wikipedia.org/wiki/Change-making_problem), for which there exist standard solution. — Bergi, Jan 19 '17 at 14:50

Tim Consolazio · Accepted Answer · 2017-01-19T14:44:27.050

When you submit "270" to this, you get an array [ 100, 100, 50, 20 ].

I'll leave the exceptions and edge cases to you to set up guards for. But this seems to meet all your straightforward cases.

        let arr = [100,50,20,10];

        let factors = [];
        let total = 270;

        arr.forEach ( d => {
            while ( total >= d ) {
                factors.push ( d );
                total -= d;
            }
        } );

        // [100, 100, 50, 20]
        console.log ( factors );

Store subset of an array using repeated values as much as possible

1 Answers1