#2 is weird, start by observing that if you've seen n/2+2 items then you're done.
You want n/2+1 equal numbers. So there needs to be a number that is repeated once after seeing n/2+2 numbers for this to be possible(and the rest must all be the same), now divide and conquer. For all possible repeating numbers, count their occurrence in the unseen n/2-2 numbers and return true or false based on the sum of occurrences on the two sides corresponding to each viable entry. the number of entries seen for which this can happen is at most n/4; apply the same n/2+3, then need to look at n/3 numbers... etc. etc., then say you look at n/2+n/4 numbers, then the number of numbers that could have repeated enough times so far is only a constant (n / (n/ 4)=4); And you have a constant time linear space algorithm. :D On Jan 25, 6:24 am, "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 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 -~----------~----~----~----~------~----~------~--~---
