Search code examples
performancealgorithmmathnumberssum

Split number into sum components

Is there an efficient algorithm to split up a number into N subsections so that the sum of the numbers adds up to the original, with a base minimum? For example, if I want to split 50 into 7 subsections, and have a base minimum of 2, I could do 10,5,8,2,3,5,17 (as well as any other number of combinations). I'd like to keep the numbers as integers, and relatively random but I'm not sure how to efficiently generate numbers that sum up to the original and don't include numbers lower than the given minimum. Any suggestions?

EDIT - Just to copy/paste my comment, the integers don't have to be unique, but I want to avoid equal sizes for all of them (e.g. 50 split into 10 equal sizes) everytime.

Solution

  • Here's an algorithm:

    1. Divide N by m where N is your number and m is the number of subsections.
    2. Round the result down to its nearest value and assign that value to all of the subsections.
    3. Add one to each subsection until the values add up to N. At this point if N was 50 and m was 7, you'd have 8, 7, 7, 7, 7, 7, 7
    4. Iterate from 0 to m-1, stepping by 2, and add a random number between -(currentValue-base) and currentValue-base. Add the inverse of that number to its neighboring bucket. If you have an odd number of buckets, then on the last bucket instead of adding the inverse of that number to its neighboring bucket, add it to all of the other buckets in a distributed manner similar to steps 2 and 3 above.

    Performance: Step 1 is O(1), Steps 2, 3, and 4 are O(m), so overall it's O(m).