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
-~----------~----~----~----~------~----~------~--~---
