tag:blogger.com,1999:blog-5871184605628305545.post5142921601272186623..comments2013-05-25T03:36:33.414-07:00Comments on Puzzled: Search for CelebrityAnonymoushttp://www.blogger.com/profile/02364548875097103884noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-5871184605628305545.post-59755327879897709682012-09-10T06:29:53.773-07:002012-09-10T06:29:53.773-07:00if there is no celebrity i will run a check whethe...if there is no celebrity i will run a check whether evrybody knows him and he know sno body,it will tkae O(n) time only.<br />In the demo i have mistyped i5 as i4 . <br /><br />Soumya Ranjan Pandahttps://www.blogger.com/profile/15736410206466516578noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-90009966306586578762012-09-10T06:21:36.553-07:002012-09-10T06:21:36.553-07:00Algo :
Let the people be i1,i2..in.
Run a progress...Algo :<br />Let the people be i1,i2..in.<br />Run a progressive check <br />compare i1 with i2 : <br />if(A(i1,i2)==1 && A(i2,i1)==0)<br />{keep i1,i2}<br />else<br />{drop i2}<br />....<br />if i2 is dropped now check i1 and i3.And so on .<br />At any point if we encounter a celebrity then he/she is not gonna get dropped + any other person encountered after him will get dropped .<br />So the last person remaining in the array is the celebrity .<br />Since the worst case is when celebrity is at index N,the worst case has N-1 comparisons .So O(n)time is reqd.<br />---------<br />Demo:<br />let the persons be <br />i1,i2 ,i3,C,i5<br />-i1 knows i2,i2 doesnt know i1,i2 and i3 dont know each oder.<br />-other relationships can be laid as reqd.<br />check i1,i2(condtion satisfied so we dnt drop any)<br />check i2,i3(condition not satisfied,drop i3)<br />check i2 C(condn satisfied dont drop any)<br />check C i4(condn not satisfied drop i4)<br />Array:i1,i2,C<---celebrity Soumya Ranjan Pandahttps://www.blogger.com/profile/15736410206466516578noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-64351630942330419132012-07-19T22:44:39.325-07:002012-07-19T22:44:39.325-07:00Algorithm(n people):
pair the people in n/2 gr...Algorithm(n people):<br /> pair the people in n/2 groups<br /> possiblePeople = empty<br /> if both of them no each other, drop them<br /> else the one who doesn't know the other --> add him to possible people<br /> return Algorithm(possiblePeople)<br /><br />mainMethod:<br /> person = Algorithm(n people)<br /> celebrityCheck(person) // he might not be a celebrity<br /><br />Since everybody knows a celebrity and celebrity doesn't know anyone, the size of the recursion will be reduced by atleast half. therefore, T(n) = T(n/2) + O(n) --> T(n) = O(n)Anonymoushttps://www.blogger.com/profile/00094235259094340406noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-56462183681566203072012-07-19T21:04:25.810-07:002012-07-19T21:04:25.810-07:00@rik : can u be more precise. from your descriptio...@rik : can u be more precise. from your description, it doesn't seems to be O(n)Anonymoushttps://www.blogger.com/profile/00094235259094340406noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-90602103711282393052012-07-18T09:13:40.380-07:002012-07-18T09:13:40.380-07:00then proceed to next person 3&4... as we are o...then proceed to next person 3&4... as we are only finding celebrity, then we don't have to bother about 1&2 ....Rikhttps://www.blogger.com/profile/16765576918216443372noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-58374979055604298682012-07-18T08:28:36.220-07:002012-07-18T08:28:36.220-07:00How about A(12)= A(21)=1 and both 1&2 not bein...How about A(12)= A(21)=1 and both 1&2 not being celebrity but knowing each otherAnonymoushttps://www.blogger.com/profile/02364548875097103884noreply@blogger.comtag:blogger.com,1999:blog-5871184605628305545.post-55469677565285076442012-07-18T05:48:29.086-07:002012-07-18T05:48:29.086-07:00one thing we must notice that there can not be mor...one thing we must notice that there can not be more than one celebrity, if we have then they know each other(as celebrity is known by all other) and they don't know each other(as celebrity doesn't know anyone)... so contradiction... <br />now we can proceed this way... we have 1-2-3-...-n people in a party... start comparing 1 & 2 (compare A(12) and A(21) ), we have either none of them as celebrity (if A(12)=A(21)=0 or 1) or one of them can be celebrity (1 can be celeb if A(21)=1, A(12)=0, ow 2 can be celeb)... suppose 1 can be celeb.. then compare 1 & 3 and find next who can be celeb.... thus at last either we will find no one as celeb. or one person k can be celeb... now check whether k is celeb. or not by checking all A(ik)and A(kj)for all i&j (as we have missed some checking in prev. process and we just found out if anyone can be celeb. or not)... thus we have our celebrity in O(n) time (actually we need 2*(n-1)+2*(n-1) checking only)...Rikhttps://www.blogger.com/profile/16765576918216443372noreply@blogger.com