On Feb 3, 2008 9:46 PM, Ridvan Gyundogan <[EMAIL PROTECTED]> wrote: > > for #2: Just create a hashtable Number-> Counts. > Make one iteration through the whole List and make > hashtable(Number)=hashtable(Number)+1. No comparisons so far. > Then if size(hashtable)<n/2 go through each element of the hashtable > and compare it with (n/2+1). > > So exactly maximum n/2+1 comparisons. The complexity is O(n) >
This method does give us the required time complexity, but we are not using constant space. I think there was a stipulation in the question that we had to use constant space, even though Kamalakannan has not specified this. Taking this into account the best method would be: Init c = 1; Init elem = first character in the array. for each element in the array (other than the first one): if currentelem == elem: c++ else: c--; if c == 0: elem = currentelem At the end of this loop, the current element specifies the element which appears n/2+1 or more times, IF c is not 0. If c is 0, no element occurs n/2 + 1 times. This takes just O(n) time, as it is just one iteration through the loop, and only uses constant space. > > > > > > > -- Aravind Narayanan | [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
