I'm not sure how to word the title properly, but the problem goes something like this:

I have 5 nodes, and node 0 is the "master".

User inputs a number, e.g. 100 to the master.

master "splits" the number into 5 parts, 0 - 20, 21 - 40, 41 - 60, 61 - 80, 81 - 100.

the nodes will then take the number, and do some calculation, and return the result back to the master.

The problem is the segmentation part. What if the number is something weird e.g. 101?

  • 1
    Divide the input number by the number of nodes, scatter the remainder among some subset of the nodes. What's so hard? (Now if the work per number is not uniform, things would get more interesting...) – user7043 Mar 3 '15 at 20:29
  • 2
    How would you distribute 101 marbles to 5 kids? – Dan Pichelman Mar 3 '15 at 20:29
  • Any way you implement the splitting, rounding will probably send the "leftovers" to one node or another automatically. Since you have 5 nodes, you have at most 4 "leftover bits", which doesn't seem like a lot, so what exactly are you concerned about? – Ixrec Mar 3 '15 at 21:31
  • I think my issue is more about implementing it in code. – Edwin Mar 3 '15 at 21:49
  • 3
    @Edwin So try implementing it. If you encounter problems, come back and ask about them. This site isn't here to write your code for you. – itsbruce Mar 3 '15 at 22:40

Your problem addresses the pidgeonhole principle (http://en.wikipedia.org/wiki/Pigeonhole_principle).

It simply sais that if you got N items and you want to put them into M containers, where N is greater than M, then at least one container has to hold at least ceil(N/M) (Where ceil(x) is the smallest integer greater than or equal to x) items.

You can solve your problem for example with the following algorithm:

    A = Array of size M
    i = remainder(N/M)
    for x from 0 to i-1
        A[x] = ceil(N/M)
    for y from i to M-1
        A[y] = floor(N/M)
    return A

This will distribute your items equally between the containers.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.