Hey, fellow programmers. Hope you all are doing good.I don't want to waste your precious time so let's cut to the chase. As you can see I'm a newbie so pardon me if what i ask is way above my league. Believe me I'm trying but this competitive programming is difficult for me but sooner or later i will become good at this.
This was one of the questions asked in Amazon Hackathon round please help me solve this. Since I'm a newbie you can also share the links to article and knowledge resources that might be required to solve this. Please do not provide code directly as answer. Let me know how to solve and approach this problem.
The question is as follows-
/*****************************************
You are given N non negative integers namely-D1,D2,D3...DN. You have to find all the labelled trees that can be constructed such that the out-degrees of each vertex(1<=i<=N) is Dn. It is guaranteed that the sum of D1,D2....Dn is N-1.
Example test case- First line is number of integer and second line contains degree of each edges. Input-
4
0 1 0 2
--------------------------------------------------------------- Output- 5
A total of 5 labelled trees can be formed with given out-degrees.
Input-
5
0 1 1 1 1
Output-
125
A total of 125 labelled trees can be formed with given out-degrees.
*************************************************************/
Now this is an interesting problem because, although it might not look so, it involves quite a bit of number theory. Since each tree node has Di edges, we want to take the gcf of all Di. This will tell us the minimum number of trees we can create. Now we can take the lcm of all Di, and our answer will simply be lcm — gcd.
hey, the input output is something like this- N-4 0 1 0 2
Output- 5
N-5
0 1 1 1 1
output-125
kindly let me know wether this will follow same logic or not.
Oops, neglect the zeros and the answer will be (lcm — gcd)!. This is because nodes with zero connections don't really matter in the grand scheme of things except for different permutations. It should run smoothly after this bug fix.
Add explanation for first test case. I able to create only such 3 trees. If w we fix the outdegree of 4th vertex(3 cases), then there is only 1 way to arrange outdegree of vertex.
It was asked in hackon with amazon hackathon. I was not able to solve this, that's why i posted it here.