An array A is said to have a majority element if more than half of the entries i

Question

An array A is said to have a majority element if more than half of the entries in A are exactly the same. Describe an O(n log n) divide-and-conquer algorithm that determines whether an array A of n items has a majority element, and if so, returns that item. The only comparison operation allowed on the items is equality. That is, your algorithm can determine whether "A[lAi or not in O(1) time, but it cannot, for example, compare the items to sort them, or hash the items into buckets. Explain why your algorithm takes O(n logn) time

Explanation / Answer

struct AVLTreeNode

{

int val;

int count;

AVLTreeNode *left,*right;

}

Algorithm:

1. Insert elements in AVL Tree one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return.

Algorithm to Construct AVL Tree:

Let the newly inserted node be w
1) Perform standard BST insert for w.
2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
a) y is left child of z and x is left child of y (Left Left Case)
b) y is left child of z and x is right child of y (Left Right Case)
c) y is right child of z and x is right child of y (Right Right Case)
d) y is right child of z and x is left child of y (Right Left Case)

Analysis:

Since the insertion of new node in an AVL tree takes O(log(n)) time, then insertion of 'n' elements will take O(nlog(n)) time.

Consider two test cases:

1,1,1,1,1,5,3,2,4.

In this case count of 1 is 5 which is more than half the total number of array elements so it's an majority element. We will increment the count of 1 along with insertion and the moment count of 1 becomes more than n/2 just return and no need to further continue the algorithm to insert the remaining elements as we already found the majority element. This is the best case of this algorithm.

5, 6, 2 ,4, 3, 5, 5, 5, 5

In this case 5 is the majority element and to get the final result as 5 we have to insert all the array elements into the AVL tree because after the insertion of last array element only in AVL tree count of 5 becomes more than half of total number of array elements. Hence in these type of situations all "n" array elements will get inserted into the AVL tree which will lead to creation of AVL Tree in O(nlog(n)) time complexity.

Time Complexity: O(nlog(n))

Algorithm Paradigm: Divide-and-Conquer

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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