Let T[1..n] he an array of n integers, where n is odd. An integer is a commonly

ID: 3562954 • Letter: L

Question

Let T[1..n] he an array of n integers, where n is odd. An integer is a commonly occuring element in T if it is equal to at least half the elements in T. For example, if T = 9,6,6,7,6, then the commonly occuring element of T is 6. For example, if T = 4,7,5,4,3, then T has no commonly occuring element. You have to write an efficient algorithm which finds out if T has a commonly occuring element, and if so to find it. In terms of efficiency, the faster your algorithm is, the better. You will get full credit if your algorithm is correct and works in time O(n log n). You will get some partial credit if your algorithm is correct and works in time more than O(n log n) (a) Give a clear description of the basic idea behind your algorithm. (b) Give the pseudocode. (c) Trace the execution of your algorithms on the two examples given above. (d) Do a worst case time analysis (use big O notation) of your algorithm.

Explanation / Answer

a) Sort the given the array, using quick sort or merge sort

now traverse the array and check if the next element is equal to the present element

if so, increment count

exit the loop if the count = n/2

if next element is not equal, re-intialize count =0

b)   #include<iostream>
#include<algorithm>
using namespace std;
int main()
{
   int n=5;
   int a[5]={4,7,5,4,3};
   sort(a,a+n);
   int count=0,common;
   for(int i=0;i<n;i++)
   {
       if(a[i]==a[i+1])
       {
           count++;

           if(count==n/2)
           {
               cout<<"common element is: "<<a[i];
               break;
           }
       }
       else
       count=0;
   }
   if(count!=n/2)
   cout<<"No common element is present";
   return 0;

}

c) in the first example; after sorting the array will be {6,6,6,7,9}

now since there are three '6'; which is equal to n/2

count becomes n/2

therefore, print the common element and exit the loop.

second example, array becomes {3,4,4,5,7}

since no of '4' is less than n/2

we dont have a common element;

d) time complexity for sorting is O (nlogn)

time complexity for traversing the array is O(n)

therefore total time complexity= O (nlogn) + O(n)

= O(nlogn)

Navigate

Let TV e N be a positive integer which can be written with k bits. In the follow

Let T_1 be the rooted tree consisting of a single root vertex. For n greaterthan

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

Let T[1..n] he an array of n integers, where n is odd. An integer is a commonly

Question

Explanation / Answer

Related Questions

Navigate