An element is called frequent if it occurs at least 2n/3 times in an array of si

Question

An element is called frequent if it occurs at least 2n/3 times in an array of size n. For example, if given input [7, 3, 7, 7, 5, 7] your algorithm should return 7 is frequent since it occurs at least 4 times. Given input [1, 5, 2, 3, 6, 6] your algorithm should return No frequent element. Given an unsorted array A of n integers, design an algorithm that determines whether there is a frequent element. For full marks your algorithm should run in O(n) time. For part marks, you can give an O(n log n) or O(n^2) algorithm. You may use any algorithm we saw in class as a subroutine. Write your algorithm below Analyse the running time of your algorithm.

Explanation / Answer

Solution a)

int main()

{
int my_arr[100], freqency[100];
int n, i, j, counter;

/*
* Read size of array and elements in array
*/
printf("Enter size of array: ");
scanf("%d", &n);

printf("Enter elements in the array: ");
for(i=0; i<n; i++)
{
scanf("%d", &my_arr[i]);
freqency[i] = -1;
}

/*
* Counts frequency of each element
*/
for(i=0; i<n; i++)
{
counter = 1;
for(j=i+1; j<n; j++)
{
if(my_arr[i]==my_arr[j])
{
counter++;
freqency[j] = 0;
}
}

if(freqency[i]!=0)
{
freqency[i] = counter;
}
}

/*
* check frequency of any element equals to 2n/3
*/
for(i=0; i<n; i++)
{
if(freqency[i]==(2*n)/3)
{
           temp=1
}
      
}
if(temp==1)
return "frequent element";
else
   return "No frequent element";
}

Solution b)

running time of this algorithm is 0(n2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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