http://placementsindia.blogspot.com/2007/12/solutions-to-few-google-top-interview.html
Different solutions exist for this problem,depending on how once perceives the question. If all the companies are assumed to be unique things,then the solution goes like this.Initially we need to merge 2 companies.These 2 can be chosen in Nc2 ways.Now in the second iteration we can merge 2 companies among the remaining N-1 in N-1c2. We go on merging like this until we have a single union of all the companies. Hence the number of ways of doing this is (Nc2)*(N-1c2)*(N-2c2) *........*(2c2)=(N!*(N-1)!)/2^(N-1) . One more way of looking at this problem is the structural aspect of merging.In the above solution suppose there are 4 companies say,to be merged. We could have merged companies 1&2 in the first iteration and 3&4 in the 2nd iteration.Likewise we could have also merged 3&4 in the first iteration and then 1&2 in the 2nd iteration.After these 2 merges,both of them are identical,though we put them as different ways in solution1,depending on which 2 were merged before the other 2.If we were interested only in the structural aspects,then the above solution doesn't even consider that. If we are interested in the number of structurally different ways to merge these, then we can confront this problem on the assumption that all the given companies are identical .Then this problem reduces to parenthesis problem,i.e number of ways of putting N pairs of parenthesis.The answer then would be N-1 th Catalan Number, i.e (2N-2)!/N!(N-1)!. If the companies aren't identical ,with some permutations also getting into the picture, then the solution isn't straightforward and we couldn't figure it out. /dufus/ On Aug 24, 11:58 pm, ankur aggarwal <ankur.mast....@gmail.com> wrote: > Merging companies > Suppose we have N companies, and we want to eventually merge them into > one big company. How many ways are there to merge? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
