Hi HC On Jan 30, 2008 12:53 AM, hc busy <[EMAIL PROTECTED]> wrote:
> > 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. > How is the number we need to keep track of at _most_ 3? I would have thought that given 3/4th of the array, one number can repeat n/4 times, and all the other elements can be unique. As I understand it you are keeping a count of repeated elements. If all the elements other than the one repeated n/4 times were unique, that would lead to linear space usage, instead of the required constant space. We can use the solution proposed by Malay Bag in an earlier message on this thread. That will work in constant space and linear time. > > > > 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. > > > -- Aravind Narayanan | [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
