Search code examples
javaalgorithmdivide-and-conquer

Divide n Conquer (Secret Sharing through minimum calls)

There are n number of students in a class. Teacher tells one secret to each student. The only way to share the secret is through a phone call. Using divide and conquer, design an algorithm to find the minimum number of phone calls required so that each student get all the secrets.

One of my friend asks me this. I put some time to make an sketch i.e. I will have an array of students , I'll break it recursively until I have one student and upon joining them back I'll make a count that a call has been made between these two.

While combining two pairs I'll count two calls and so on. This is the point which is troubling to me or may be here I am missing something.

X1 X2  (1 call)               
X3 X4 (1 call)

X1 -----> X3
X2 -----> X4 (2 more calls)

Any assistance is appreciated.

Solution

  • The optimum scheme for n>=4 people to share all n pieces of information is 2n-4 as shown in this paper.

    The divide and conquer approach to this problem is illustrated as follows:

    For four persons A, B, C and D, say, take conversations AB, and CD, followed by AC and BD. For every additional person P, schedule one conversation AP, before A, B, C and D interchange their knowledge, and another conversation AP afterwards.