# Coming Up with a Good Algorithm for a Simple Idea

Posted
by
mkoryak
on Stack Overflow
See other posts from Stack Overflow
or by mkoryak

Published on 2012-09-22T01:27:02Z
Indexed on
2012/09/25
3:38 UTC

Read the original article
Hit count: 254

I need to come up with an algorithm that does the following:

Lets say you have an array of positive numbers (e.g. `[1,3,7,0,0,9]`

) and you know beforehand their sum is 20.

You want to abstract some average amount from each number such that the new sum would be less by 7.

To do so, you must follow these **rules**:

- you can only subtract integers
- the resulting array must not have any negative values
- you can not make any changes to the indices of the buckets.

The more uniformly the subtraction is distributed over the array the better.

Here is my attempt at an algorithm in JavaScript + underscore (which will probably make it n^2):

```
function distributeSubtraction(array, goal){
var sum = _.reduce(arr, function(x, y) { return x + y; }, 0);
if(goal < sum){
while(goal < sum && goal > 0){
var less = ~~(goal / _.filter(arr, _.identity).length); //length of array without 0s
arr = _.map(arr, function(val){
if(less > 0){
return (less < val) ? val - less : val; //not ideal, im skipping some!
} else {
if(goal > 0){ //again not ideal. giving preference to start of array
if(val > 0) {
goal--;
return val - 1;
}
} else {
return val;
}
}
});
if(goal > 0){
var newSum = _.reduce(arr, function(x, y) { return x + y; }, 0);
goal -= sum - newSum;
sum = newSum;
} else {
return arr;
}
}
} else if(goal == sum) {
return _.map(arr, function(){ return 0; });
} else {
return arr;
}
}
var goal = 7;
var arr = [1,3,7,0,0,9];
var newArray = distributeSubtraction(arr, goal);
//returned: [0, 1, 5, 0, 0, 7];
```

Well, that works but there must be a better way! I imagine the run time of this thing will be terrible with bigger arrays and bigger numbers.

**edit**: I want to clarify that this question is purely academic. Think of it like an interview question where you whiteboard something and the interviewer asks you how your algorithm would behave on a different type of a dataset.

© Stack Overflow or respective owner