Hi Amit , Creating a binary tree for n element takes o(nlogn) not o(logn). we can understand it by one examples lets have an array 1,2,3 ,4 ,5 ,6,7,8 try to create the binary tree it required more than 8 comparison
it is a nothing but a sorting. after putting element in binary tree if we traverse the tree inorder we will get the element in ascending order. I feel your algo also takes nlogn times. Regards Praveen Amit Banwari wrote: > Hi Praveen. > > May be this can help u. > > Create a Binary tree with array[N/2] as the root. > > Have every node in the tree be composed of { value and no of times } > where value is the value of the array element and the no of times > denotes the number of > occurrences. > > Visit each node one by one and all nodes left to ROOT are less than > root and all > nodes greater are to the right of ROOT. > > If a value is repeated u will reach there again and again and increment it. > After incrementing just check if it is greater than N/2 > If yes you have the value, if no carry on. > > **adding n elements in a binary tree is O(log n) > > Thanks > amit > > > On 6/20/06, Praveen <[EMAIL PROTECTED]> wrote: > > > > Hi guys, > > > > Please help in solving this problem. > > > > u have given an array . U need to find out the element which > > has > > occurred more than N/2 times where N is the array length. > > > > for ex in an array 3,4,1,3,3,3,2,6,3 ans is 3 > > try to do it in o(N) > > > > I am able to do it in O(nlogn ) > > > > my solution is first sort this array > > > > then u would be having array like this > > > > 1,2,3,3,3,3,3,4,6 > > > > after that u can use the following logic to find the element > > > > for (int i =0;i<N/2;i++) > > { > > if(a[i] == a[i+N/2]) > > return a[i]; > > } > > > > is there any better method for this. > > > > Regards > > Praveen > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---