You are given an array of size N, where an element has a higher frequency than any other element in the array. Specifically, that element occurs at least N/2+1 times. You are not allowed to compare elements in the array, however you are allowed to check if any two elements are equal.

You are to design a randomized algorithm that returns the element with the highest frequency in such an array in linear time.

a) Complete the following pseudo-code to accomplish this task. (20 points) HighestFrequencyElement(Input: array A of length N) While True i = random(1,N) // chooses a random number between 1 and N