we can use voting algorithm this.. maintain a variable count and a variable index.now make a scan for 1 to n-3.during a scan initialize count with 1 and index with 0.now if a[i]==a[index] then increment count else decrement count.when count reached 0.start again incrementing it when u get a new element and also update the indexes. now when the loop terminates then u might have got a suitable candidate.now u have to make 3 more scans in order to check the frequency of arr[index],arr[n-1] and arr[n].
On Sat, Jun 30, 2012 at 6:41 PM, saurabh singh <saurab...@gmail.com> wrote: > > @above > > >> On Thursday, 28 June 2012 04:05:12 UTC+5:30, 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. >>> >>> >> On Thursday, 28 June 2012 04:05:12 UTC+5:30, 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. >>> >>> >> On Thursday, 28 June 2012 04:05:12 UTC+5:30, 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/-/0myz4OIStO8J. >> >> 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. >> > > -- > 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 > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Regards Lomash Goyal * * -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
