Non negative set subtraction

Question

This applies to any language, but I'd be implementing it in node.

I have a set of integers, and a value that I need to subtract from the sum of the set.

[4, 5, 6, 7, 8] - 25

If we subtract from every number evenly, we'd get:

[-1, 0, 1, 2, 3]

However, I don't want any numbers less than 0. So, if I were writing an algorithm to do this, the negative numbers would overflow equally into the remaining numbers, and we'd now have:

[0, 0, 1, 2, 3] - 1

Making the resulting set:

[0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333]

Is there any fast operation or series of operations that don't involve looping until completion to solve this problem?

Note that this is exactly the outcome I want. All of the negative values overflow EVENLY into the remaining positive values.

I use Lodash so an answer in Lodash would be acceptable.

Answer 1

You can reduce a lot of the loops needed, assuming the number set

1. Only has positive values
2. The sum of the set is more than the value to subtract
3. It can be sorted.

On point 3. you said in comments that it's fine to sort this, so here is the algorithm I have in mind. It's verbose in terms of variable names but hopefully it makes it clearer. All in all, it's not too complex:

const result = subtractFromSet([4, 5, 6, 7, 8], 25);
console.log(result)

function subtractFromSet(numberSet, totalToSubtract) {
  return numberSet.map((currentMember, index, wholeSet) => {
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    return currentMember - toSubtract;
  })
}

To explain it in words, here is what is happening

1. Subtracting a value from the sum of the set is the same as subtracting the value divided by the size of the set from each member. So [4, 5, 6, 7, 8] - 25 would be 4 - 5, 5 - 5, 6 - 5, etc.
2. If we don't want negatives, then we only subtract up to the current member. So with current member 4 and the average being 25 / 5 = 5, we can only subtract 4.
3. In order to spread the remainder, we simply add it back to the total remaining to subtract for the rest of the members. So when we get to the second member 5, the average is now (25 - 4) / (5 - 1) because we couldn't subtract the full 5 average the first time, only 4, and the remaining elements are one less. This yields 5.25.

And so when going through each member and adjusting the total then average needed to subtract, we get the correct result. Although, be aware of floating point arithmetic in programming, as it can lead to results that are slightly off. If you round up to enough significant figures for your needs, you can largely avoid that.

One final thing - as I said, the input has to be sorted. This can be easily done like so:

const unsortedArray = [6, 4, 7, 8, 5];
const sortedArray = unsortedArray.sort((a, b) => a - b)

console.log(sortedArray);

I left it out from the above algorithm to focus on what we actually do with the sorted input.

The total complexity of this algorithm is pretty decent - a decent sorting would net you O(n log(n)) time complexity. Depends on the sorting implementation and the dataset - 5 elements are likely to be sorted via an O(n^2) Bubblesort but then again, it's 5 element, so it's probably not going to have an impact. Running the subtraction algorithm is a simple O(n). The space complexity for subtraction is O(2n) because .map() makes a copy of the array. I chose this as it's a bit cleaner because you still have the input. But you can also do the subtraction in-place with minimal changes and it would net you a O(n) space complexity.

const input = [4, 5, 6, 7, 8];
subtractFromSet(input, 25);
console.log(input);

function subtractFromSet(numberSet, totalToSubtract) {
  numberSet.forEach((currentMember, index, wholeSet) => { //using .forEach instead of .map
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    wholeSet[index] = currentMember - toSubtract; //modify the array directly
  })
}

Answer 2

It is not clear what "efficient" is intended to mean at the question.

For an algorithm you can

• .map() input array to input arr array of integers or decimals minus n number divided by input .length, map

• .filter() results of map array to elements where the value is greater than 0, not

• .filter() elements of map array to elements greater than or equal to 0, .matches

• .reduce() not array to sum of elements less than 0, subtotal

• pass subtotal to Math.abs() to get absolute value of integer, divided by matches.length minus not.length to get the subtrahend to be applied to input, N

• .map() map, where minuend value is less than or equal to 0 return 0, else return value minus N, with .toFixed(3) chained to meet requirement of 3 decimal digits described as expected output, cast to number with add + operator, result

• return result

const nonNegativeSubtraction = (arr, n) => {
  const map = arr.map(x => x - (n / arr.length));
  const not = map.filter(x => x < 0);
  const matches = map.filter(x => x >= 0);
  const subtotal = not.reduce((a, b) => a + b);
  const N = Math.abs(subtotal) / (matches.length - not.length);
  const result = map.map(x => x <= 0 ? 0 : +(x - N).toFixed(3));
  return result;
}

const test = [0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333];

let input = [4,5,6,7,8]; // minuend

let n = 25; // subtrahend

let res = nonNegativeSubtraction(input, n); // result

console.log(res);

console.assert(JSON.stringify(test) !== JSON.stringify(res), [test, res]);

Answer 3

No sorting required, but using recursion.

let output = substract( [6,5,7,4,8], 25, 5)
console.log(output)
output = substract( [6,5,7,4,8.5], .10, 5)
console.log(output)
function substract(array, substractThis, length) {
 let delta = substractThis/length;
 let toSubstract;
 let out = array.map(ele => {
  toSubstract =  Math.min(ele, delta);
  substractThis -= toSubstract;
  ele = ele - toSubstract;
  length -= !ele;
  return ele;
 });
 if(substractThis < 1) {
  return out
 }
 return substract(out, substractThis, length)
}

Answer 4

I have come with this solution that uses recursion. It does not need to pre-sort the array to work, however that will cause the algorithm can't take some advantages. Explanations are within the code...

const spreadSubtract = (arr, val) =>
{
    // Get the numbers of positive (> 0) elements on the array.

    let len = arr.filter(x => x > 0).length;

    // Get the new subtract value.

    let sub = val / len;

    // Stop condition: if the positive (> 0) elements on the
    // array minus the subtract value are all positive (> 0),
    // then return the mapped array.

    if (!arr.some(x => x > 0 && x - sub < 0))
    {
        return arr.map(x => x > 0 ? x - sub : x);
    }
    
    // Get the minimum element on the array that will be
    // negative when subtracting <sub> from it.

    sub = Math.min(...arr.filter(x => x > 0 && x - sub < 0));

    // Proceed to next iteration of the recursion.

    return spreadSubtract(
        arr.map(x => x > 0 ? x - sub : x),
        val - sub * len
    );
}

// OP example:
console.log(spreadSubtract([4, 5, 6, 7, 8], 25));

// Another test:
console.log(spreadSubtract([0, 9, 1, 5, 3], 11));

// Test subtract greater than the sum of array values:
console.log(spreadSubtract([4, 0, 1, 2, 5], 20));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

And here is one approach you can use when the array is sorted in ascending order:

const spreadSubtract = (arr, val) =>
{
    let avgSub = val / arr.length;

    return arr.map((x, idx) =>
    {
        if (x < avgSub)
        {
            avgSub = (val -= x) / (arr.length - idx - 1);
            return 0;
        }
        else
        {
            return x - avgSub;
        }
    });
}

// Tests
let test1 = [[4, 5, 6, 7, 8], 25];
let test2 = [[0, 9, 1, 5, 3], 11];
let test3 = [[4, 0, 1, 2, 5], 20];

// Note array are sorted first.
console.log(spreadSubtract(test1[0], test1[1]));
console.log(spreadSubtract(test2[0].sort(), test2[1]));
console.log(spreadSubtract(test3[0].sort(), test3[1]));

.as-console {background-color:black !important; color:lime;}
.as-console-wrapper {max-height:100% !important; top:0;}

Answer 5

You could take a single loop approach for an ordered array and have a look to the changing value for dispersing.

function subtract(array, delta) {
    return array.map((v, i, { length }) => {
        var d = delta / (length - i);
        delta -= Math.min(v, d);
        return Math.max(0, v - d);
    });
}

console.log(subtract([4, 5, 6, 7, 8], 25));