Similar to majority voting problem...
Assume there exits a majority element....
As only one such element is possible...
Algo: A[1..n]
int Major(A[1..n]){
Majority=a[1];
count=1;
for(i=2;i<=n;i++)
{ if(majority ==a[i])
count++;
else
{ if(count==0)
{ majority = a[i];
}
else
count--;
}
}
return majority;
}
On Thu, Sep 30, 2010 at 1:33 PM, Christi Massey <[email protected]>wrote:
> Q.Assume you have an array A[1:n] of n elements.A majority element of a is
> any element occuring in more than n/2 positions(so if n=6 or n=7, any
> majority element will occur in at least 4 positions).assume that elements
> cannot be ordered or sorted, but can be compared for equality.(you might
> think of elements as chips ,and there is a tester that can be used to
> determine whether or not chips are identical)
> Design an efficient algorithm to find a majority element in A(or determine
> that no majority element exists).
> May this problem be design in O(n) time?if yes,how?
>
> --
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"
--
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?hl=en.
