You are given an array of size N, where an element has a higher frequency than a

Question

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

Explanation / Answer

Solution:

Algorithm:

HighestFrequencyElement(Input: array A of length N) {

While True

count = 0;

i = random(1,N) // chooses a random number between 1 and N

for(int j=0; j<N; j++){ // for every element in the array compare if the element is equal to the random elemnt

if A[i] == A[j] //comparing if the elemnts are equal

count++; //if the above condition is true

}

if(count==(N/2)+1)

return A[i]; //The element is found and we are returning it

}

The above algorithkm is checking randomly for the most frequenct element inside the array by randomly selecting one elemnt from the array and comparing with every other elemnt in the array to check if it is occuring exactly N/2+1 times in the array and returning it.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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