for question no. 2 median wil be the answer because repeated element is one more than the half of the no. of element for finding medain we can use modified quick sort which uses the fact that we have to go only one side depending on the no. of element we found on that side. in general algo will perform better , worst case scenario may be different.
On Jan 25, 2008 7:54 PM, kamalakannan .h <[EMAIL PROTECTED]> wrote: > hai guys these questions were asked in anna university onsite programming > contest. > 1) find the second biggest number in a given array of size n. you have to > use n+logn number of searches or less > > 2) how will you find out if a number is repeated (n/2+1) times in an > array of size n? the complexity should be o(n). > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
