Consider the MosTFREQUENTELEMENT problem below. Note that in this problem, there

Question

Consider the MosTFREQUENTELEMENT problem below. Note that in this problem, there are two parameters n and k that dictate the constraints on the input instead of just the array size n. Positive integers n and k, along with an arrav A of n integers in the range 1,k] The value a E (1,2,3,... , k) with the largest number of occurrences in the array A. If multiple elements are tied for the largest number, choose x to be the smallest such element. Input: Output: For example, with n 10. k-6 and A-4, 3, 6, 4, 4, 1, 3, 64, 11, the result is 4. (a) Give pseudocode for a O(n + k) algorithm which solves MoSTFREQUENTELEmenT. Briefly justify both the correctness and the running time of the algorithm (you do not need to provide a formal proof, but you must convincingly demonstrate both points).

Explanation / Answer

Let the input array be named "arr".Make an array named freq of size k as the range of the input is from 1 to k.This array will hold the frquency of every element where index number+1 of this array acts as the element.Initialise this array as 0.In initialising the array,we traversed k elements.

Now,traverse the input array and do freq[ arr[i]-1 ]++; that is increment the frequency of the element.Note we did arr[i]-1 to map 1 to k from 0 to k-1 as index of freq can be from 0 to k-1.We traversed n elements

Now again traverse the freq array keeping track of maximum frequency.Consider the code shown below for this step-

//Initialise element with maximum frequency as element 1(denoted by index 0)

max=0;

for(i=1; i<k; i++)

{

//Compare the maximum frequency till now with frequency of current element and update if needed

if(freq[max] < freq [i] )

max=i;

}

This step traverses k elements.

Hence time compexity of this algorithm is O(n+k).

Hope i have answered your question satisfactorily.Leave doubts in comment section if any.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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