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 <masseychri...@gmail.com>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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 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.