I found a similar solution looking somewhere else. The solution for this problem is: a. There can be atmost 3 elements (only 3 distinct elements with each repeating n/3 times) -- check for this and done. -- O(n) time. b. There can be atmost 2 elements if not above case.
1. Find the median of the input. O(N) 2. Check if median element is repeated N/3 times or more -- O(n) - *{mark for output if yes}* 3. partition the array based on median found above. - O(n) -- {partition is single step in quicksort} 4. find median in left partition from (3). - O(n) 5. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* 6. find median in right partition from (3). - O(n) 7. check if median element is repeared n/3 times or more - O(n) *{mark for output if yes}* its 7*O(N) => O(N) solution. Constant space. we need not check further down or recursively. {why? reason it.. its simple} On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote: > > > Design an algorithm that, given a list of n elements in an array, finds > all the elements that appear more than n/3 times in the list. The algorithm > should run in linear time > > ( n >=0 ). > > You are expected to use comparisons and achieve linear time. No > hashing/excessive space/ and don't use standard linear time deterministic > selection algo. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/OYZtR1iwbGQJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.