[algogeeks] Re: ALgo help pls
In my opinion also, this is a Majority vote algorithm as mentioned by Navin and as coded by Dave. Only point I would add to @Dave's code is that it wont be possible to find if the majority element has 2n/3 occurance as majority element keeps changing during the run and as the majority algorithm tells you a number which has greater than n/2 occurrence. So all you need to do is another liner scan after the majority element is found to check if its count is 2n/3. @Narsimha Raju: your failure to find 2n/3 occurrence by adding a for loop is expected. Please reply if we are able to add a for loop into code above (given by @Dave) to find if majority element has 2n/3 occurance. Thanks, Sourav On Sep 22, 9:02 am, Navin Naidu wrote: > Use majority vote algorithm: > > http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html > > > > On Wed, Sep 22, 2010 at 9:12 AM, pre wrote: > > Hi all, > > pls help me solve this problem.. > > Design an algorithm to find the majority element of an array.. > > majority element must be an element tht has the cardinality greater > > than 2n/3 where n is the number of elements in the array and the time > > complexity must be a linear time.. ie o(n).. > > > hint : use mode or median to solve .. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Thanks & Regards, > > - NMN -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ALgo help pls
Using hashing we can't do it? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALgo help pls
@ Narsimha Raju : yes only one such can element exit...
@Pre :
Is there any algorithm to find median or mode in o(n)...
because common approach are :
Find the Median of: 9, 3, 44, 17, 15 (Odd amount of numbers)
Line up your numbers: 3, 9, 15, 17, 44 (smallest to largest)
The Median is: 15 (The number in the middle)
Find the mode of:
9, 3, 3, 44, 17 , 17, 44, 15, 15, 15, 27, 40, 8,
Put the numbers is order for ease:
3, 3, 8, 9, 15, 15, 15, 17, 17, 27, 40, 44, 44,
The Mode is 15 (15 occurs the most at 3 times)
On Wed, Sep 22, 2010 at 8:01 AM, Narsimha Raju wrote:
> @coolfrogs: How can more than one element exist of 2n/3 times repeated..
> @dave: can u add that for loop and send as i tried but could not succeed
>
> On Wed, Sep 22, 2010 at 6:23 PM, coolfrog$ <
> dixit.coolfrog.div...@gmail.com> wrote:
>
>> solution in o(n log n)
>> can be ( as if solution exit only one element cam be a majority element
>> in the given array)
>> 1. sort the array in O(nlogn)
>> 2. x = a[2n/3]
>> if(a[0]==x)
>> { if(x== a[(2n/3])+1)
>> return (x)
>>
>> }
>> On Wed, Sep 22, 2010 at 5:53 AM, Dave wrote:
>>
>>> Try something like this:
>>>
>>> int FindMajority( int n , int a[] )
>>> {
>>>int majority = a[0];
>>>int count = 1;
>>>for( i = 1 ; i < n ; ++i )
>>>{
>>>if( a[i] == majority )
>>>{
>>>++count;
>>>}
>>>else
>>>{
>>>if( count == 0 )
>>>{
>>> majority = a[i];
>>> count = 1;
>>>}
>>>else
>>>{
>>> --count;
>>>}
>>>}
>>>}
>>>return majority;
>>> }
>>>
>>> It will find an element that occurs at least n/2 times in the array.
>>> If you need to verify that the element occurs 2n/3 times, add a loop
>>> to count the number of occurences of majority before the return.
>>>
>>> On Sep 21, 10:42 pm, pre wrote:
>>> > Hi all,
>>> > pls help me solve this problem..
>>> > Design an algorithm to find the majority element of an array..
>>> > majority element must be an element tht has the cardinality greater
>>> > than 2n/3 where n is the number of elements in the array and the time
>>> > complexity must be a linear time.. ie o(n)..
>>> >
>>> > hint : use mode or median to solve ..
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Regards,
> C. Narsimha Raju
> MS, IIIT Hyderabad.
> http://research.iiit.ac.in/~narsimha_raju/
Re: [algogeeks] Re: ALgo help pls
@coolfrogs: How can more than one element exist of 2n/3 times repeated..
@dave: can u add that for loop and send as i tried but could not succeed
On Wed, Sep 22, 2010 at 6:23 PM, coolfrog$
wrote:
> solution in o(n log n)
> can be ( as if solution exit only one element cam be a majority element in
> the given array)
> 1. sort the array in O(nlogn)
> 2. x = a[2n/3]
> if(a[0]==x)
> { if(x== a[(2n/3])+1)
> return (x)
>
> }
> On Wed, Sep 22, 2010 at 5:53 AM, Dave wrote:
>
>> Try something like this:
>>
>> int FindMajority( int n , int a[] )
>> {
>>int majority = a[0];
>>int count = 1;
>>for( i = 1 ; i < n ; ++i )
>>{
>>if( a[i] == majority )
>>{
>>++count;
>>}
>>else
>>{
>>if( count == 0 )
>>{
>> majority = a[i];
>> count = 1;
>>}
>>else
>>{
>> --count;
>>}
>>}
>>}
>>return majority;
>> }
>>
>> It will find an element that occurs at least n/2 times in the array.
>> If you need to verify that the element occurs 2n/3 times, add a loop
>> to count the number of occurences of majority before the return.
>>
>> On Sep 21, 10:42 pm, pre wrote:
>> > Hi all,
>> > pls help me solve this problem..
>> > Design an algorithm to find the majority element of an array..
>> > majority element must be an element tht has the cardinality greater
>> > than 2n/3 where n is the number of elements in the array and the time
>> > complexity must be a linear time.. ie o(n)..
>> >
>> > hint : use mode or median to solve ..
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Regards,
C. Narsimha Raju
MS, IIIT Hyderabad.
http://research.iiit.ac.in/~narsimha_raju/
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALgo help pls
solution in o(n log n)
can be ( as if solution exit only one element cam be a majority element in
the given array)
1. sort the array in O(nlogn)
2. x = a[2n/3]
if(a[0]==x)
{ if(x== a[(2n/3])+1)
return (x)
}
On Wed, Sep 22, 2010 at 5:53 AM, Dave wrote:
> Try something like this:
>
> int FindMajority( int n , int a[] )
> {
>int majority = a[0];
>int count = 1;
>for( i = 1 ; i < n ; ++i )
>{
>if( a[i] == majority )
>{
>++count;
>}
>else
>{
>if( count == 0 )
>{
> majority = a[i];
> count = 1;
>}
>else
>{
> --count;
>}
>}
>}
>return majority;
> }
>
> It will find an element that occurs at least n/2 times in the array.
> If you need to verify that the element occurs 2n/3 times, add a loop
> to count the number of occurences of majority before the return.
>
> On Sep 21, 10:42 pm, pre wrote:
> > Hi all,
> > pls help me solve this problem..
> > Design an algorithm to find the majority element of an array..
> > majority element must be an element tht has the cardinality greater
> > than 2n/3 where n is the number of elements in the array and the time
> > complexity must be a linear time.. ie o(n)..
> >
> > hint : use mode or median to solve ..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ALgo help pls
Try something like this:
int FindMajority( int n , int a[] )
{
int majority = a[0];
int count = 1;
for( i = 1 ; i < n ; ++i )
{
if( a[i] == majority )
{
++count;
}
else
{
if( count == 0 )
{
majority = a[i];
count = 1;
}
else
{
--count;
}
}
}
return majority;
}
It will find an element that occurs at least n/2 times in the array.
If you need to verify that the element occurs 2n/3 times, add a loop
to count the number of occurences of majority before the return.
On Sep 21, 10:42 pm, pre wrote:
> Hi all,
> pls help me solve this problem..
> Design an algorithm to find the majority element of an array..
> majority element must be an element tht has the cardinality greater
> than 2n/3 where n is the number of elements in the array and the time
> complexity must be a linear time.. ie o(n)..
>
> hint : use mode or median to solve ..
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
