Geekly Articles each Day
📜 ⬆️ ⬇️

Yandex test task

Task


Write a function that from an arbitrary input array selects all combinations of numbers whose sum is 10.

At first glance, the task is simple, all you need to do is write a recursion and sort through all the values.

Or you can use a binary increment, but in order to iterate over all the values ​​for a vector of numbers of length N, it takes 2 ^ n iterations.
')
First, we choose a special case, suppose that the array consists of numbers> 0. Later, based on this example, we will implement all cases.

STEP 1


a) Consider one of the special cases - the sum of all elements of the array <10.
The logic is simple, sum (V) <10, then sum (V) -V [i] <sum, that is, if the sum of the combinations will always be less than 10.

b) If sum (V) = 10, then the sum sum (V) -V [i] <sum. The result will be only one v .

STEP 2


We remove all unnecessary from the vector

As an example, take the array [13, 10, 20, 13, 13, 18, 2, 9, 5, 8, 8, 9, 2, 1, 8, 16, 4, 15, 2, 2, 2, 1, 5 , 5, 5].

It immediately shows that it makes no sense to look for combinations if the value is> 10, but everything will become immediately clear. if we sort it:

[1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10, 13, 13, 13, 15, 16, 18, 20 ]

At this stage, we can already know for sure that we need to delete all elements greater than 10
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9, 10]

But in fact, everything is a little more interesting. we need to limit the vector to the value so that V [0] + V [i] <= 10; where i tend to N; But if V [i] = 10, then we add 10 to the result
v => [1, 1, 2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 8, 8, 8, 9, 9]

STEP 3


There are duplicate elements in an already filtered array. If we decompose a vector into sub vectors, and calculate their sum, we get something like this
[1,1] => 2
[2, 2, 2, 2, 2] => 10
[4] => 4
[5, 5, 5, 5] => 20
[8, 8, 8] => 24
[9.9] => 18

The essence of my thoughts is that it does not make sense to consider combinations of repeating numbers if their number * value> 10. That is, we cut off the vectors until their sum is less than 10, and add those that are 10 to the result:
[1,1] => [1,1]
[2, 2, 2, 2, 2] => [2, 2, 2, 2]
[4] => [4]
[5, 5, 5, 5] => [5]
[8, 8, 8] => [8]
[9.9] => [9]

As a result of the 3rd step, our vector will be as follows
[1, 1, 2, 2, 2, 4, 5, 8, 9]

As you can see, the size of the vector has decreased from 25 to 9, it is much smaller (remember the number of iterations);

With negative numbers


This is a bit more complicated. we will assume that we have implemented the function of finding combinations for a positive sorted vector based on the previous restrictions.
comb (arr, sum), where sum is the required amount, arr is a vector sorted from positive numbers

For example, take the vector:
[19, 15, -9, 3, -13, -8, -12, 11, -2, -10, 0, 7, 17, -17, -14, -15, -11, -6, -12 , -10, 9]

1. Break the vector
A = only positive values
B = only negative values
And also see if we have values ​​= 0

2. Sort
Sort vectors (positive ascending, negative descending)

We check the particular case for positive numbers (STEP 1)

3. Verification of positive
Check for positive values
comb (B, 10)

3. Check for negative
create combinations of all negative numbers, but with a restriction:

(sum of elements modulo) <(sum of all positive) + 10
we find combinations for the NEW reference amounts (the sum of the elements modulo + 10)

4. Equality 0
If the source vector has a value of 0, then we add all combinations + 0 to the result;

As a result of such limitations, on average, when testing values ​​with an array of 28 and 1000 tests long, the time gain is almost 42%

Be careful not to look nervous. The author is not responsible for moral suffering.
function combine(arr, etalon = 10) { //--------------------------------------------// //------------- helpers --------------------// //    // Create binnary array function createBin(length) { let bin = []; for (let i = 0; i < length; i++) { bin[i] = false; } return bin; } //   1 //Binnary add 1 bit function binAddBit(bin, i = 0) { if (i >= bin.length) { return null; } if (bin[i] == false) { bin[i] = true; return bin; } else { bin[i] = false; i++; return binAddBit(bin, i); } } function iniq(arr) { let result = []; let object = {}; arr.forEach(vector => { value = vector.sort(function(a, b) { return a - b }); key = value.join(','); object[key] = value; }); for (var key in object) { result.push(object[key]); } return result; } //   // : //       //       //       function _combine(arr, sum = 10) { let result = []; //   if (arr[0] > sum) return []; if (arr[0] == sum) return [ [sum] ]; //1.   let $aKey = {}; let $a = []; let $sum = 0; //    $aKey[arr[0]] = arr[0]; $a.push(arr[0]); $sum += arr[0]; let $eqSum = false; for (let i = 1; i < arr.length; i++) { if ((arr[i] + arr[0]) <= sum) { //-----------------------------// // count*element < sum $aKey[arr[i]] = $aKey[arr[i]] != undefined ? $aKey[arr[i]] += arr[i] : arr[i]; if ($aKey[arr[i]] < sum) { $a.push(arr[i]); $sum += arr[i]; } //-----------------------------// //-----------------------------// // count*element = sum if ($aKey[arr[i]] === sum) { let $res = []; for (let j = 0; j < (sum / arr[i]); j++) { $res.push(arr[i]); } result.push($res); } //-----------------------------// } if (arr[i] == sum) { $eqSum = true; } } if ($eqSum) { result.push([sum]); } if ($sum < sum) return result; if ($sum == sum) { result.push($a); return result; } //   let bin = createBin($a.length); while (change = binAddBit(bin)) { let $sum = 0; let $comb = []; for (let i = 0; i < change.length; i++) { if (change[i] == false) continue; $sum += $a[i]; if ($sum > sum) break; // exit in accumulate $comb.push($a[i]); if ($sum == sum) { result.push($comb); } } } return result; } //------------- helpers --------------------// //--------------------------------------------// let result = []; //         //   -   let zero = false; //       let posetive = []; let negative = []; let sumPosetive = 0; arr.forEach(element => { if (element === 0) { zero = true; } if (element < 0) { negative.push(element); } if (element > 0) { posetive.push(element); sumPosetive += element; } }); //   ( ) posetive.sort(function(a, b) { return a - b }); negative.sort(function(a, b) { return b - a }); //       ,  //       if (sumPosetive < etalon) return []; //       if (sumPosetive == etalon) { result.push(posetive); if (zero) { let _clone = posetive.slice(); _clone.push(0); result.push(_clone); } return result; } //      ; result = result.concat(_combine(posetive, etalon)); // SUPPLE -          combinPosetiveLim negative = negative.filter(function(value) { return -value <= (sumPosetive + etalon); }); //    (  ) let bin = createBin(negative.length); //   while (changeBin = binAddBit(bin)) { let sum = etalon; let vector = []; //      for (let i = 0; i < changeBin.length; i++) { if (changeBin[i] == false) continue; sum -= negative[i]; vector.push(negative[i]); } if (sum > (sumPosetive + etalon)) continue; let lines = _combine(posetive, sum); lines.forEach(value => { result.push(vector.concat(value)); }); } //    0 if (zero) { result.forEach(item => { let _clone = item.slice(); _clone.push(0); result.push(_clone); }); } result = iniq(result); return result; }

Source: https://habr.com/ru/post/460923/

More articles:


All Articles