Coming Up with a Good Algorithm for a Simple Idea
- by mkoryak
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.
