A majority element in an array, A$,$ of size N is an element that appears more than N$/2$ times $($thus$,$ there is at most one$).$

For example, the array $3,3,4,2,4,4,2,4,4$ has a majority element $(4).$

Conversely, the array $3,3,4,2,4,4,2,4$ does not.

If there is no majority element, your program should indicate this. Here is a sketch of an algorithm to solve the problem:

First, a candidate majority element is found $($this is the harder part$).$ This candidate is the only element that could possibly be the majority element. The second step determines if this candidate is actually the majority. This is just a sequential search through the array. To find a candidate in the array, A$,$ form a second array, B$.$ Then compare A$1$ and A$2.$ If they are equal, add one of these to B; otherwise do nothing. Then compare A$3$ and A$4.$ Again, if they are equal, add one of these to B; otherwise do nothing. Continue in this fashion until the entire array is read. Then recursively find a candidate for B; this is the candidate for A $($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 in pseudocode to compute the majority element.