GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
353 views
The number of ways , in which numbers 1,2,3,4,5 can be inserted into binary heap,such that resultant binary heap is max heap ?

given ans :8
asked in Programming by Veteran (12.9k points)   | 353 views
should'nt it be 4??
given is 8 , m getting 9

2 Answers

+8 votes
Best answer
Yes, It is 8. [ Thanks @Kapil , @Sonam :) ]  

1. 5, 4, 3, 2, 1

2. 5, 4, 3, 1, 2

3. 5, 3, 4, 2, 1

4. 5, 3, 4, 1, 2

5. 5, 4, 1, 2, 3

6. 5, 4, 1, 3, 2

7. 5, 4, 2, 3, 1

8. 5, 4, 2, 1, 3.
answered by Veteran (25k points)  
selected by
i did with permutation which you considered but writing all cases ,..  but it will take time and if you miss any case then it will give wrong ans ,

i did like first fix 5 as root( 1 way) then , at 2nd level 3,4 node so there 2 cases

1) when 3 is 2nd node then 3rd node fixed 4 and other 2 nodes either 1,2 (2 ways)

2) when 4 is 2nd node then remainning nodes will pe arrange in 3! way = 6 ways

so total 6+2+1 =9 , yes ans is 8 but where i am leaking ?
yes , given soln is same in test series.
5 fixed not a case here.

until we go upto leaf , we cannot consider a way.
Ok... :) Keep in mind

This is through Brute Force... Is there any formula?

+2 votes
Answer wil be 8 only . First th will be fixed to the root .

Now it is difficult to see from the internal nodes see from leaves. The remaining elements are (1,2,3,4). There will be 2 leaves possible. So possible pairs will be .

if we choose (1,2) in leafs then the possiblity for its root is (3 or 4) . So 2 choices for root and 1,2 can also be arranged in 2 ways - total choices = 2*2 = 4
like wise

(1,3) - 1 choice i.e 4. but arrangement of 1,3 or 3,1 possible - 2*1 choices - 2

(1,4 ) not possible

(2,3) - 1 choice = 1*2 = 2 choices

(2,4) not possible

(3,4) not possible

total ways = 4+2+2 = 8 choices
answered by Veteran (13.8k points)  
Thanks


Top Users Jul 2017
  1. Bikram

    3782 Points

  2. manu00x

    2464 Points

  3. Debashish Deka

    1832 Points

  4. joshi_nitish

    1494 Points

  5. Arnab Bhadra

    1096 Points

  6. Arjun

    1054 Points

  7. Hemant Parihar

    1050 Points

  8. Shubhanshu

    972 Points

  9. Ahwan

    876 Points

  10. akash.dinkar12

    642 Points


23,953 questions
30,895 answers
70,107 comments
29,272 users