# How do I have a group of numbers which total does not exceed a limit, and each number must be >= 0?

Suppose I have an array of n numbers. The rules for the array is as below:

1. All the numbers must add up to 1000
2. If a number changes (positive or negative), all the other numbers in the array must be adjusted so that the sum of the array is still 1000
3. The hard part - all numbers must be greater than or equal to 0.

Number 1 and 2 can be easily done by getting the delta of change, and spreading the delta among the other numbers. The trick is condition 3.

There's a question asking for its application. The numbers are percentages to be fed into pie chart; the user can adjust each pie segment with a slider. As it is a pie chart using percentages, all the sliders must add up to 100% - meaning if the user drag the slider to reduce the size of one pie slice, all the other pie slices should increase. No slice of the pie should be less than 0 or more than 100.

• Thanks for the catch, it's a typo on my part. All numbers must be greater than 0. – Extrakun Jan 8 '16 at 7:45
• why are you finding this difficult? what's the application? seems like a pretty artificial problem, i.e. homework – kevin cline Jan 8 '16 at 7:58
• Edited the question to add in the application – Extrakun Jan 8 '16 at 8:13
• This is really a UX problem, and there just so happens to be a stack exchange for that :D – gardenhead Jan 8 '16 at 9:10
• Obviously some changes are not possible - if there are N objects then no object can be changed to a value less than 1 or greater than 1000 - N + 1, so such a change must be rejected. – gnasher729 Jan 8 '16 at 9:18

Basically, your range is 0 to 1000. When one value is changed, your new range is 0 to sum(N). You want to then normalize to 0 to 1000. So you compute the fraction of the total for each value and then multiple by 1000. Each value is thus multiplied by 1000/sum(N). Here's an example:

``````[100,100,300,500]
``````

Now suppose we change one value:

``````[100,300,300,500] # sums to 1200
``````

Now multiple each value by 1000/1200. (The range you want divided by the sum you have.)

``````[83, 250, 250, 417] # sums to 1000
``````

Updated

As @AProgrammer points out, depending on how you round, you may be off by one. You probably want to use the floor as a result and then add one to entries until you reach the desired sum. Or alternatively, if the APIs that consume this can use floating point values, use those.

• Honestly, reducing each slice by a fraction, instead of an outright subtraction, is something I have not thought of. - it also take care of the >= 0 requirement. – Extrakun Jan 8 '16 at 8:44
• the first row [100,200,300,500] sums up to 1100, not 1000. – Pieter B Jan 8 '16 at 9:23
• "Note that to make this work, you need to use traditional rounding rules, not integer math." It's more complex (consider [400, 400, 400] if you don't take the other values into account, you have a sum of 999 or of 1002). You need to truncate and then distribute the excess. – AProgrammer Jan 8 '16 at 10:05
• You can be off by nearly .5 per number. – Deduplicator Jan 8 '16 at 21:47

As a programming problem, there are lots of easy answers to this; three quick brainstormed ones:

• When you increase a slice, decrease the size of the last slice with a size greater than zero by an equivalent amount.
• When you increase a slice, decrease the size of the largest slice by an equivalent amount.
• When you increase a slice, decrease the size of all other slices in proportion to their current values. For example, if your slices where currently sized (10, 20, 30, 40) and you increased the 40 slice to 46, distribute this reduction among the other slices in the ratio 1:2:3 so you end up with (9, 18, 27, 46).

And fairly obvious equivalent algorithms for decreasing a slice.

However, this is probably more interesting as a UX problem - which algorithm produces the most "intuitive" behaviour? As such, it may be worth asking at User Experience.