An array A[1...n] is said to have a majority element if more than half of its en

Question

An array A[1...n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form is A[i] > A[j]? (Think of the array elements as jpeg files, say.) However you can answer questions of the form: is A[i]=A[j]? in constant time. Show how to solve this problem in On log n) time. Does knowing the majority elements of Al and A_2 help you figure out the majority element of A? If so, you can use a divide-and-conquer approach. Can you give a linear-time algorithm Pair up the elements of A arbitrarily, to get n/2 pairs (with possibly one left over element. Look at each pair: if the two elements) are different, discard both of them; if they are the same, keep just one of them. Show that if n is even and A has a majority element, say a, then a is also a majority element among the left over elements after the above procedure (However, it could be that after the above procedure, there is a majority element that is not a majority element of A. Therefore, if you recursively find a majority element among the remaining elements, you will need to verify that it is indeed a majority element in A.) If n is odd, you have to deal separately with the final non-paired element.

Explanation / Answer

A.

MajorityElement(A):

Split array in two halves A1 and A2

Each part recursively Call MajorityElement

untill it has only one element. If one element then return that eleemnt as majority for single element array

At every other level it will get return value from its two recursive calls

So majority element will either be in left half or right half

- if both half's return no majority then their is no majority

- If right side is majority and left isn't. So only this value could be possible majority element at this level (sub part). Count number of element equal to this element in combined array. If not majority return no majority else return this to next level.

- If left has majority but not left. Same as above

- If both return majority then count occurence of both. If either of them is majority return that to next level else no majority

At each level two calls are made to each half and and we compare each element max twice so 2n total comparison.

So recurrence will be

T(n) = 2T(n/2) + 2n

Solving will give O(nlogn)

B.

After each iteration we will either have majority element in leftover array or no majority element

reason

If elements are not same we can remove both of them. If that element is majority it will still have occurence

(if n is odd then even if all majority element are paired with other element then also one odd one will remain if it exists)

(If n is even, then majority is n/2 + 1, so half of array cannot be paired in a wway to discard majority as majority element will remain as max of n/2 -1 element can pair with n/2-1 majority element and one pair of majority element causing them to remain only)

So after every step we will have majority element.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.