[algogeeks] Re: find the most occured (more than N/2 times , where N is the length of the array) element in an array

Tue, 20 Jun 2006 19:04:34 -0700

Oh..sorry...i thought it's >=N/2 elemets.... :-)
And....what about the modified version of the example given in the question
3,4,1,3,3,3,2,6,5,5?

If i understood karthik's logic correctly, it must lead to
step 1 : (3,4),(1,3),(3,3),(2,6),(5,5)
step2 : 3,5
step 3: NIL (Soultion)

Is it right?
Please correct me if i am wrong....

Regards,
Vikram



On 6/21/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote:

Please read the question properly...The number can be a majority
element only if it repeats more than n/2 times....In your example it
doesnt...

On 6/20/06, Vikram Venkatesan < [EMAIL PROTECTED]> wrote:
> Hi,
>
> The problem with that PAIRING solution is that, at each step, some
> information is lost....
> Say, the array is 2,5,2,7,2,8,2,1
> While taking elements pair by pair, first, since 2 !=5 , we skip it... (At
> this step itself, the information about the occurence of '2' is lost)....
> The same happens in the further steps too... Finally, we end up with a 'NO
> SUCH NUMBER' answer for this array, which is not the expected ans....
>
> Vikram
>
>
> On 6/20/06, Pradeep Muthukrishnan <[EMAIL PROTECTED]> wrote:
> >
> > I guess what guillaume said is pretty much fine and works in O(n) and
> > as he said there is no need for stack
> > so the algo is pretty straight
> > assume 1st element is the majority element and set a counter to 1
> > compare with next element and if they are same increment counter else
> > decrement counter
> > if counter reaches 0 then assume next element is majority element and
> continue
> >
> > finally whatever number is chosen may not be the majority element so
> > once again run thro the arry and find if it occurs more than n/2
> > times. so O(n)!!
> >
> >
> > On 6/20/06, Googmeister <[EMAIL PROTECTED] > wrote:
> > >
> > >
> > > Praveen wrote:
> > > > Hi Arun ,
> > > >
> > > >             it is not a median. it is the element which has occured
> > > > more than N/2 time in an array.
> > > >
> > > >           median tellls half of the element are greter then median
> > > > value and half of the element has lesser value than median.
> > >
> > > If there were a majority, it would also be the median element.
> > >
> > >
> > > >
> > >
> >
> >
> > > >
> >
>



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

Reply via email to