A majority element in an array, A, of size N is an element that appears more thanN/2

Chapter 2, Problem 2.26

(choose chapter or problem)

A majority element in an array, A, of size N is an element that appears more thanN/2 times (thus, there is at most one). For example, the array3, 3, 4, 2, 4, 4, 2, 4, 4has a majority element (4), whereas the array3, 3, 4, 2, 4, 4, 2, 4does not. If there is no majority element, your program should indicate this. Hereis a sketch of an algorithm to solve the problem:First, a candidate majority element is found (this is the harder part). This candidate is theonly element that could possibly be the majority element. The second step determines ifthis candidate is actually the majority. This is just a sequential search through the array. Tofind a candidate in the array, A, form a second array, B. Then compare A1 and A2. If theyare equal, add one of these to B; otherwise do nothing. Then compare A3 and A4. Again ifthey are equal, add one of these to B; otherwise do nothing. Continue in this fashion untilthe entire array is read. Then recursively find a candidate for B; this is the candidate forA (why?).a. How does the recursion terminate?b. How is the case where N is odd handled? c. What is the running time of the algorithm?d. How can we avoid using an extra array B? e. Write a program to compute the majority element