mokoto's blog

By mokoto, history, 4 months ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm stuck getting TLE. Can anyone provide a link of solution to the above problem? Help will very much appreciated

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I want a link to the solution of the above problem. Thanks in advance.