edited by
53,616 views
89 votes
89 votes
The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________
edited by

16 Answers

12 votes
12 votes

The answer is based on computing minimum and maximum in pairs of two 

say number of elements in even and array is 

   5 1 2 5 6 8 9  10

than code goes as follows

fun(){

   int mn,mx;

   if(arr[0]>arr[1]){  mn=arr[1];mx=arr[0];} // 1 comparison for 2 elements

   else{ mx=arr[1];mn=arr[0]; }

   for(int i=2;i<n;i=i+2){ // picking every  pair of element

       // we will calculate the minimum and maximum of this pair and then compare with global minimum and maximum hence total of 3 comparisons for a pair

      int t_mn,int t_mx; 

       if(arr[i]>arr[i+1]){ t_mn=arr[i+1]; t_mx=arr[i];} // 1st comparison 

     else {  t_mn=arr[i]; t_mx=arr[i+1];}

   if(mx>t_mx) mx=t_mx; // 2nd comparions

   if(mn<t_mx) mn=t_mx; // 3rd comparioson

}

cout << mx << " " <<  mn << endl;

return 0;

}

hence if n is number of elements

  than comparisons=1+((n-2)/2)*3

hence in n=100 ans=148                     

similarly in odd number of elements 1st element will be max as well as min

  hence comparisons=((n-1)/2)*3

refer to CLRS book

8 votes
8 votes
Algorithm for finding minimum and maximum:

If n is odd then initialize min and max as first element.
If n is even then initialize min and max as minimum and maximum of the first two elements
respectively.
For rest of the elements, pick them in pairs and compare their
maximum and minimum with max and min respectively.

this is  same as the tournament method .

 

So when n is odd, number of comparisons = 3*(n-1)/2
when n is even, number of comparisons = [3*(n)/2] - 2 = 3*50-2 = 148.
7 votes
7 votes

Consider n=8 elements in an array {1,4,5,8,3,2,7,9}
Lets make a tournament bracket for them, where at each stage the winner is the minimum element between the two.
 

As you can see, number of comparisons being done = n-1 = 7 

Similarly, to find the maximum element you again will need n-1 comparisons!
So total no of comparisons to find min and max=2(n-1)
Hmm...there is one optimisation to it !!

The last level in the tree is making n/2 comparisons(4 in this case) and these are being repeated while finding the minimum and maximum! 

So doing the last level comparisons only once, we do n/2 comparisons less
Hence 2(n-1) - n/2 = 2n-2-n/2 = 3n/2-2.

 

So, here n= 100

Using 3n/2-2 = 150-2 = 148

Answer:

Related questions

0 votes
0 votes
1 answer
2
Raghav Khajuria asked Oct 13, 2018
323 views
Minimum no of comparisons required to find the minimum and maximum of n distinct elements
1 votes
1 votes
1 answer
3
mystylecse asked Aug 15, 2017
3,449 views
The minimum number of comparisons required to find the minimum and maximum of 60 numbers is..............
0 votes
0 votes
1 answer
4
Aspi R Osa asked Dec 14, 2015
1,511 views
Consider a set of 20 elements.To find maximum and minimum element in the given set, the minimum number of comparisons required is _________? (using DAC Max-Min algorithm)...