### mokoto's blog

By mokoto, history, 12 months ago, ,

Given an array of size n consisting of n-1 distinct elements.In other words there is exactly one element that is repeated.It is given that the element that would repeat would be either the maximum element or the minimum element. Find the number of structurally different max heaps possible using all the n elements of the array that is max heap of size n.

Let us take an example with array array elements as

1 5 5

The possible max heaps using the given elements are:- First: 5 on the root. 1 as the left child of root and 5 as the right child of the root

5

/ \

1 5

Second: 5 on the root. 5 as the left child of root and 1 as the right child of the root.

5

/ \

5 1

second example : N = 6, 1 1 2 3 4 5 ans = 11.

N = 5 , 1 1 2 3 4 ans = 4 N can be upto 1000.

when integers are all different T[N] = (n-1)C(left) * T[L] *T[R] , but what will be the recusion in this case.

• 0

 » 9 months ago, # | ← Rev. 2 →   0 I'm stuck getting TLE. Can anyone provide a link of solution to the above problem? Help will very much appreciated
•  » » 9 months ago, # ^ |   0 i cant give you the problem link as problem is open to me only. you can give me your solution.why do you want link. problem is same as above.
•  » » » 8 months ago, # ^ |   0 I want a link to the solution of the above problem. Thanks in advance.