I think there was a typo. I wanted to say its a "constant space, linear time algorithm" instead of "constant time linear space algorithm" Maybe that helps to make sense of it.
Well, one must find a number that repeats at least twice after seeing n/2+2 numbers, (then require the rest to be that same number) But this is hard, because there could be ~ n/4 of them. So, we take the algorithm to look through 3/4 of the array, that way we just need to find one number who repeats n/4 times, and the number of those that we need to keep track of is at most 3, because, well, because there's only enough space in 3n/4 to repeat 3 numbers each at least n/4 times. On Jan 29, 4:50 am, "Mahesh Gunda" <[EMAIL PROTECTED]> wrote: > Hi HC, > > Here, In this sentence > 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) > > How did u find this number ? > > k bye > > On Jan 26, 2008 3:32 AM, hc busy <[EMAIL PROTECTED]> wrote: > > > > > > > #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). > > -- > With regards > G.Mahesh > Software Engineer > webMethods, Bangalore. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
