How to find the lowest possible combination of keys within an array

Question

I have an array that will always have 6 keys: var ary = [5,10,28,50,56,280]. I have a variable defined as limit I want to check it against.

I want to find the lowest possible combination or sum of keys from this array that is above limit. We'll call this result.

A bit of constraints I am trying to work within:

1 result can be a single key itself: Such as If limit = 0 the lowest possible combination or sum of keys should default to the lowest key it can find which would be ary[ 0 ]. in this case or 5.

2 result can be a combination of any keys: If limit = 11, result would = ary[ 0 ] + ary[ 1 ] ( 5 + 10 ). which would be 15.

3 And lastly, result can be above the greatest sum of ary: result = 5 + 10 + 28 + 50 + 56 + 280; // equals 429 In this case limit would be 430

Note: Any key can be repeated as many times as it has to before it surpasses result.

My attempts in progress:

function add(a, b) { //add all keys in array
    return a + b;
}

var combine = function(a, min) { //find all combinations of array
    var fn = function(n, src, got, all) {
        if (n == 0) {
            if (got.length > 0) {
                all[all.length] = got;
            }
            return;
        }
        for (var j = 0; j < src.length; j++) {
            fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all);
        }
        return;
    }
    var all = [];
    for (var i = min; i < a.length; i++) {
        fn(i, a, [], all);
    }
    all.push(a);
    return all;
}

var subsets = combine([5,10,28,50,56,280], 1);
var limit = 11;

for( var i = 0; i < subsets.length; i++ ){
  document.write('combination: ' + subsets[ i ] + ' sum: ' + subsets[ i ].reduce(add, 0) + '<br>');
}

Will the array always have 6 items, or do you have to allow for efficiency in processing much larger arrays? What if `limit` is higher than the largest possible sum? Return `undefined`, or...? — nnnnnn, Oct 25 '16 at 02:20
@nnnnnn For the purposes of this small program it will always have 6 items. There is no largest possible sum because that number is infinite, as keys can be reused over and over again. I'll update my question. — , Oct 25 '16 at 02:25
This looks like an interview question, and the solution can be based off of the same idea as the `max sum subarray`. On Stackoverflow, it's important that you show some code that you tried and what progress you made. — Mouad Debbar, Oct 25 '16 at 02:30
@MouadDebbar Thanks for the feedback. Not an interview question but I'll update my attempts as I am still learning much about JS. — , Oct 25 '16 at 02:31
This is a variation of Subset Sum problem. Please refer http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ and this should help to some extent — yuvanesh, Oct 25 '16 at 02:35
What would be the result if the limit is 44? Would it be `[50]` or `[10, 28]`? — , Oct 25 '16 at 03:09
@PeterLeger The result if limit was 44 should be the lowest key or combination of keys the function can find that sits **above** 44. So the answer should be 48. 28 + 10 + 10 — , Oct 25 '16 at 03:12
@carb0nshel1 so any key may be repeated while finding the combinations? — kukkuz, Oct 25 '16 at 05:10
@kukkuz Yes. I'll update my question. Any key should be allowed to be repeated until it surpasses `result`. Of course, it should still be the lowest possible value to surpass `result` — , Oct 25 '16 at 05:12

user3297291 · Accepted Answer · 2016-10-25T16:47:07.447

1

I think this works. Can you provide more test cases? The expected 429 > 434 from your answer should be 429 > 430, right?

var findLowest = function(arr, limit) {
    if (limit < arr[0]) return arr[0];

    // If there's a number in our arr that's higher than the limit,
    // this is the initial benchmark
    var bestCandidate = Infinity,
        maxIndex = arr.findIndex(v => v > limit);

    if (maxIndex !== -1) {
        bestCandidate = arr[maxIndex] - limit;
        arr = arr.slice(0, maxIndex);
    }

    // Calculate remainders, call this method recursively for all remainders
    var diffs = arr.map(v => limit % v);

    var finalDiffs = diffs.map(v => findLowest(arr, v) - v);
    
    return limit + Math.min(bestCandidate, finalDiffs.sort()[0]);
    
};

var prepareData = function(arr) {
    return arr
        // Remove duplicates of nrs in array
        .reduce((res, v) => {
            var needed = !res.length || res.every(r => v % r);
            return needed ? res.concat(v) : res;
        }, [])

        // Generate each combination (length * length - 1)
        .reduce((res, v, i, all) => {
            return res.concat(v).concat(all.slice(i + 1).map(v2 => v + v2));
        }, [])
        
        // Sort lowest first
        .sort((a, b) => a - b);
}

var data = [5,10,28,50,56,280];
var testCases = [
    [data, 5, 10],
    [data, 11, 15],
    [data, 25, 28],
    [data, 50, 53],
    [data, 55, 56],
    [data, 1, 5],
    [data, 281, 282], // 9 * 28 + 5 * 6
    [[50, 60, 110], 161, 170]
];

testCases.forEach(tc => {
    var prep = prepareData(tc[0]);
    var result = findLowest(prep, tc[1]);

    if (result !== tc[2]) {
      console.log("Limit: ", tc[1]);
      console.log("Expected: ", tc[2]);
      console.log("Result: ", result);
      console.log("----");
    }
});

Note: my current try is recursive, which might not be ideal... If it passes all your tests, we could rewrite it to not be recursive.

edited Oct 25 '16 at 16:47

answered Oct 25 '16 at 11:19

user3297291

22,592
4
29
45

You are right. 429 would = 430. This is the first to past all of my test cases so far. Very solid code. Doing a little more testing and tweaking it to show the numbers it is using to add. Thanks :) – Oct 25 '16 at 14:59
I feel like there are still some cases I didn't cover, but can't think of the right test to make it fail... Fun but hard problem to solve! – user3297291 Oct 25 '16 at 15:04
Thanks! I've been trying to edit your code so it shows what numbers it is adding so I have a better idea what is going on. – Oct 25 '16 at 16:15
A limit of `500` produces a result of `501`. Which I'm pretty sure is impossible to get by summing up any of those numbers, repeating or not. – Oct 25 '16 at 19:09
89 x 5 + 56 = 501 – user3297291 Oct 25 '16 at 22:01
Where do you get the 89 from – Oct 25 '16 at 22:02
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/126670/discussion-between-carb0nshel1-and-user3297291). – Oct 25 '16 at 22:06
I see how you got 89. 56 + 28 + 5. This function does what I asked. Thank you. – Oct 25 '16 at 23:20
Great to see the question solved - +1. @user3297291 It would be nice to add an explanation now too as I find it hard to understand the magic – kukkuz Oct 26 '16 at 01:50
@user3297291 Yeah, it would be much appreciated if you could somehow show what numbers you are adding. I've tried to break apart your code and fail :(. Also here is a question related to this one that shows what I am eventually trying to accomplish: http://stackoverflow.com/questions/40255189/a-counter-keeping-track-of-multiple-values-inside-an-array – Oct 26 '16 at 15:12
I tried to tackle this question without any theoretical knowledge about the problem; now I see this link in the other answer https://en.wikipedia.org/wiki/Change-making_problem Seems to me that you should port the python code to javascript to get the best result. My approach kind of resembles a "greedy" one, according to the article. I'll see if I can edit it to log the combination though. Also, note that I've included a test that still fails: 181 -> (28 * 4) + (5 * 34) – user3297291 Oct 27 '16 at 07:25

kukkuz · Answer 2 · 2016-10-25T03:01:10.953

0

So here is a solution using nested forEach loops:

var ary = [5, 10, 28, 50, 56, 280];

function lowestSum(limit) {
  var thisArg = {sum: 0};

  ary.forEach(function(ele1, index1) {
    if (ele1 > limit && (ele1 < this.sum || this.sum === 0))
      this.sum = ele1;
    ary.forEach(function(ele2, index2) {
      if (index1 !== index2 && ele1 + ele2 > limit 
          && (ele1 + ele2 < this.sum || this.sum === 0)) {
        this.sum = ele1 + ele2;
      }
    }, this);
  }, thisArg);
  return thisArg.sum;
}

console.log(lowestSum(6));
console.log(lowestSum(11));
console.log(lowestSum(27));
console.log(lowestSum(28));

edited Oct 25 '16 at 03:01

answered Oct 25 '16 at 02:20

kukkuz

41,512
6
59
95

I overlooked this. Doing a bit more testing. Thanks already though this is brilliant. – Oct 25 '16 at 03:18
Still fails in certain situations though. I'm editing my question again and searching for better ways. You came very close. – Oct 25 '16 at 03:42
Any high numbers like `400` return a `result` that's off like `0` – Oct 25 '16 at 14:41
Another question: if `limit` is say 500, is the `result` will be 429? – kukkuz Oct 25 '16 at 15:08
No, the result should always be **above** the limit. – Oct 25 '16 at 15:09
There are a lot of conditions at play here... I'll have another go tomorrow morning. – kukkuz Oct 25 '16 at 15:09
Sorry got a bit confused there, will have a look later on, thanks! – kukkuz Oct 25 '16 at 15:11
@ downvoter please come to light and give us a reason? – kukkuz Oct 25 '16 at 18:16
you may find interest: http://stackoverflow.com/questions/40255189/a-counter-keeping-track-of-multiple-values-inside-an-array – Oct 26 '16 at 15:12

pscuderi · Answer 3 · 2016-10-25T03:09:47.510

If you have a small array and thus don't care much about efficiency then you can do the following.

generate candidate pairs
sort the candidate pairs by their sum

loop through the sorted pairs until you find one over your limit

var limit = 39;
var ary = [5,10,28,50,56,280];

function getLowestCombinationOverLimit(ary, limit) {
     var i, j, p;
     var pairs = [];
     for(i = 0; i < ary.length; i++) {
         for(j = i + 1; j < ary.length; j++) {
             pairs.push({x:ary[i], y:ary[j]});
         }
     }
     pairs.sort(function (a, b) {
         return (a.x + a.y) - (b.x + b.y);
     });
     for (i = 0; i < pairs.length; i++) {
         p = pairs[i];
         if (p.x + p.y > limit) {
             return p;
         }    
     }
     return null;
 }

 console.log(getLowestCombinationOverLimit(ary, limit));

Thanks for your post. I'm testing this with different values for limit and it doesn't seem like it works every time. I will update my question in case you misunderstood it. — , Oct 25 '16 at 03:01

Low Flying Pelican · Answer 4 · 2016-10-25T12:09:56.220

0

Sort the array
Iterate the array largest value first, reducing the most closest value from the limit until limit goes below 0

function calcSumOfLowestComponents(ary,limit){
  ary.sort(function(a,b) {
    return a - b;
  });

  var safeCount = 0;

  var components = [];
  var remainder = limit + 1;
  while (remainder > 0){
    var found = false;
    for( var i = ary.length - 1 ; i >= 0; i-- ){
      if (remainder > ary[ i ]){
        var closeHigh = i != ary.length - 1 ? ary[i + 1] : ary[i];
        var closeLow = ary[i];
        if (closeHigh - remainder > remainder - closeLow){
          components.push(closeLow);
          remainder -= closeLow;  
        }
        else{
          components.push(closeHigh);
          remainder -= closeHigh;  
        }
        found = true;
      }
    }
    if (!found && remainder > 0){
      components.push(ary[ 0 ]); 
      remainder -= ary[ 0 ];
    }
    
    if (safeCount > 1000){
      break;
    }
    safeCount++;
  }
  return { total : limit + 1 - remainder, components : components};
}

function dumpData(array,value){
  var result = calcSumOfLowestComponents(array,value);
  document.write("Value = " + value + " Total = " + result.total + " Components " + result.components + "</br>");
}

var array = [5,10,28,50,56,280];
dumpData(array,2);
dumpData(array,5);
dumpData(array,11);
dumpData(array,25);
dumpData(array,28);
dumpData(array,50);
dumpData(array,55);
dumpData(array,281);
dumpData(array,429);

Result

Value = 2 Total = 5 Components 5
Value = 5 Total = 10 Components 5,5
Value = 11 Total = 15 Components 10,5
Value = 25 Total = 28 Components 28
Value = 28 Total = 33 Components 28,5
Value = 50 Total = 55 Components 50,5
Value = 55 Total = 56 Components 56
Value = 281 Total = 285 Components 280,5
Value = 429 Total = 430 Components 280,56,56,28,10

edited Oct 25 '16 at 12:09

answered Oct 25 '16 at 03:47

Low Flying Pelican

5,974
1
32
43

Checking this in multiple use cases...looks promising. – Oct 25 '16 at 03:57
This is flawed. If I input the value `25`, instead of getting `30` I get 43. Working on tweaking your code. – Oct 25 '16 at 05:03
Too late to edit my last comment but if I input a value of `25` I should get `28`. Not `30`. – Oct 25 '16 at 05:16
Updated the answer to address the 25 – Low Flying Pelican Oct 25 '16 at 12:10
Thanks for edit. A similar issue happens when the result is `33` instead of returning `35` ( 5 + 5 + 5 + 5 + 5 + 5 ), it returns `38`. I'm looking into first finding all combinations of the array using something like this: http://codereview.stackexchange.com/questions/7001/generating-all-combinations-of-an-array. Also fixed an error in my question. Like you show 429 would equal 430. – Oct 25 '16 at 14:47
Shouldn't 33 result in 10+10+10+5? – Low Flying Pelican Oct 25 '16 at 20:23
Yeah. Sorry. The result should be `35` and it should be arrived at using 10 + 10 + 10 + 5 because that is the fastest way to get there. PS. I updated my question and trying an approach that cycles through every single combination in the array and adds keys until it surpasses the `limit` – Oct 25 '16 at 20:26
See the linked question if you still have interest. – Oct 26 '16 at 15:13

How to find the lowest possible combination of keys within an array

4 Answers4

Linked