5 votes 5 votes A level of a max heap (containing 100 nos) is choosen randomly, on its selection, a node from the same level is choosen randomly. What is the probability that it is the 36th smallest element DS data-structures binary-heap probability numerical-answers + – vivek9837 asked Oct 7, 2016 • recategorized Jul 7, 2022 by Lakshman Bhaiya vivek9837 1.2k views answer comment Share Follow See all 15 Comments See all 15 15 Comments reply dd commented Oct 7, 2016 reply Follow Share 0.087 ? 0 votes 0 votes Prabhanjan_1 commented Oct 7, 2016 reply Follow Share 0.0038 ? 1 votes 1 votes vivek9837 commented Oct 7, 2016 reply Follow Share There will be 7 levels in a max heap with 100 elements. The 36th smallest element will be in the last level (with 37 elements), also it could be either of these 37 elements So the probabilty that we choose 36th smallest element will be 1/7 * 1/37 = 1/259 = 0.0038 Correct me if I am wrong 1 votes 1 votes Prabhanjan_1 commented Oct 7, 2016 reply Follow Share where is this question taken from ? i too did the same thing but debashish got a diff answer. 0 votes 0 votes dd commented Oct 7, 2016 reply Follow Share if numbers are from 1-100 (inclusive) then '36' can be in 2nd level. 0 votes 0 votes vivek9837 commented Oct 7, 2016 reply Follow Share I haven't taken it from any where kinda thought of it by myself 0 votes 0 votes dd commented Oct 7, 2016 reply Follow Share I am not sure about my answer, although 0 votes 0 votes Prabhanjan_1 commented Oct 7, 2016 reply Follow Share debashish please explain your approach ,if 36 is in 2nd level then atlast the resultant tree willn't be complete binary tree thus it's not a heap ..?? 0 votes 0 votes dd commented Oct 7, 2016 i edited by dd Oct 7, 2016 reply Follow Share In the heap : right subtree contains 36 elements, left subtree contains 63 elements. If we assign number 36 to the right child of the root, then remaining 35 numbers in the right subtree can be filled up using [1,35]. Please mention if anything wrong ! And further , if numbers are in between [1,100], then '36' can be at any level from 2 to 7. (not at the same time of course) 1 votes 1 votes Prabhanjan_1 commented Oct 7, 2016 i edited by Prabhanjan_1 Oct 7, 2016 reply Follow Share yes, u r correct ..then we can calculate like 1 / 6 (2nd level prob + 3rd level prob + 4th level prob + 5th level prob + 6th level prob) i.e., we can chose either from 2nd level or 3rd level or 4th or 5th or 6th , is it correct ?? 0 votes 0 votes Kapil commented Oct 7, 2016 i edited by Kapil Oct 7, 2016 reply Follow Share ........... 0 votes 0 votes dd commented Oct 7, 2016 reply Follow Share what I did is P = $\frac{1}{7}*0 + \frac{1}{7}*\frac{1}{2} + \frac{1}{7}*\frac{1}{4} + \frac{1}{7}*\frac{1}{8}+ \frac{1}{7}*\frac{1}{16}+ \frac{1}{7}*\frac{1}{32}+ \frac{1}{7}*\frac{1}{37} = 0.087$ Suggestion and correction plz ! 1 votes 1 votes papesh commented Oct 7, 2016 reply Follow Share @Debashish Deka u r correct... having one dout ... 36 at level 2 is at fixed location at right end and having only one choice..here u takes probability=1/2 since this level having 2 ele. now at level 3 having 4 elements ...but at this level 36 can be at any place ... u takes probability=1/4 here having 4 choices... confusing probability for me! plz explain ! 0 votes 0 votes Kapil commented Oct 8, 2016 reply Follow Share @Debashish , why 36 occurs in any level from 2 to 7. 0 votes 0 votes vivek9837 commented Oct 13, 2016 reply Follow Share @debashish, can you make that an answer 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Its P(65th largest element given that a level is chsen and an elemwnt is chosen from it) So P= ((1/7)*(1/37))/((1/7)+(1/7)*(1/2)+......+ (1/7)*(1/2^5)+(1/7)*(1/37)) P=0.0135 vishwajit_vishnu answered Oct 8, 2016 vishwajit_vishnu comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes According to me, 36 can be present at any level except @0th, hence p= probablity of choosing 36th smallest element provided any level is choosen p= 1/7∗(1/2+1/4+1/8+1/16+1/32+1/37) p= 0.1422 rish1602 answered Aug 18, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.