current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote -1 down vote favorite

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?

share|improve this question
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...) –  delnan Mar 3 at 20:29
2  
How would you distribute 101 marbles to 5 kids? –  Dan Pichelman Mar 3 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 at 21:31
    
I think my issue is more about implementing it in code. –  Edwin Mar 3 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 at 22:40

1 Answer 1

up vote 1 down vote accepted

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:

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

This will distribute your items equally between the containers.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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