2. keep a counter n take the first element of the array say e and initialize the counter n=1 for each remaining number in the array if n==0, e=current element, n=1 if current element is equal to e, n++ else n--
if n==0 there is no number otherwise check the number of occurrences of e in the array >n/2 then e output e otherwise there is no number This is known algo... I forgot the name... On Jan 26, 2008 12:38 AM, Dave <[EMAIL PROTECTED]> wrote: > > Regarding problem 2: If you really require o(n) rather than O(n), then > you can't even look at all of the entries in the array. > > If you know that one number appears multiple times and all of the > other numbers are unique, then you do it in O(n) by looking for two > adjacent numbers that are equal. That would have to be the one > repeated value, and you can then count the number of occurrences in > the array. If there are no adjacent equal values, then there cannot be > n/2+1 equal values. > > I don't have an algorithm yet that will work in O(n) if there can be > multiple repeated values and you have to find out if one of them is > repeated n/2+1 times. > > Dave > > On Jan 25, 8: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). > > > -- " I would love to change the world, but they won't give me the source code. " --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
