The Gateway to Computer Science Excellence

+48 votes

The minimum number of comparisons required to find the minimum and the maximum of $100$ numbers is ________

0

+1

Notice --> Question is asking minimum number of comparison required and nothing is given about input.

So if some one is thinking about (n-1) then it is not correct. because (n-1) will come if input has some special property.(Here n=100)

So Thanks to @Card Wizard for giving good answer.

+2

Some other related questions are -->

https://gateoverflow.in/27198/tifr2014-b-10

+58 votes

Best answer

We can solve this question by using **Tournament Method Technique** -

1. To find the smallest element in the array will take $n-1$ comparisons $= 99.$

2. To find the largest element -

- After the first round of Tournament , there will be exactly $n/2$ numbers $= 50$ that will loose the round.
- So, the biggest looser (the largest number) should be among these $50$ loosers.To find the largest number will take $n/2 - 1$ comparisons $= 49.$

Total $99+49 = 148.$

+5

After the first round of Tournament , there will be exactly n/2 numbers = 50 that will loose the round

How it is, please explain??

+4

@Shubhanshu consider 100 players and a match has to be played between two players. Hence matches = 50. Now every match will have a winner(minimum) and loser(maximum). After first set of match, there will be 50 losers, our task is boiled down to selecting biggest loser among losers(50).

+59 votes

Ans: minimum number of comparison require to find minimum and maximum is: Approach is divide and conquer ....

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2T(2) = 1 // if two element then compare both and return max and min T(1) = 0 // if one element then return both max and min same

If $n$ is a power of $2$, then we can write $T(n)$ as:

T(n) = 2T(n/2) + 2

After solving above recursion, we get

T(n) = (3/2)n - 2

Thus, the approach does $(3/2)n -2$ comparisons if $n$ is a power of $2$. And it **does more than $(3/2)n -2$ comparisons if $n$ is not a power of $2$**.

**So, here in this case put $n=100$ and we will get $(3/2)(100) - 2 = 148$ comparison ..... **

0

If we do not consider divide n conquer:

and the keys are in sorted order, then we can find the min and max in 99 comparisons.Even the iitkgp solutions said that answer is 148 but i dont know why they havent considered the ''99 comparison'' case which is minimum.

and the keys are in sorted order, then we can find the min and max in 99 comparisons.Even the iitkgp solutions said that answer is 148 but i dont know why they havent considered the ''99 comparison'' case which is minimum.

0

we can: suppose the input is in increasing order,then the following code will only take 99 comparisons.

min=max=a[0];

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

{

if (a[i]>=max)

max=a[i];

else

min=a[i];

}

i.e here ,the code will never execute the else part becuz the i/p is in increasing order(non-decreasing order).

min=max=a[0];

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

{

if (a[i]>=max)

max=a[i];

else

min=a[i];

}

i.e here ,the code will never execute the else part becuz the i/p is in increasing order(non-decreasing order).

+3

We cannot assume a special case for input (it should work for all inputs)

(i.e., we have to find the min. number of comparisons in the worst case)

(i.e., we have to find the min. number of comparisons in the worst case)

+2

i thought by min, it meant best case.

like in binary search,

minimum no. of comparisons to find the element is 1.

like in binary search,

minimum no. of comparisons to find the element is 1.

+2

@arjun sir ,

how you formed below equations

**T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2 ** T(2) = 1 // if two element then compare both and return max and min T(1) = 0 // if one element then return both max and min same

+11

Here, we are actually splitting up the problem into two small problems, so we have 2T(n/2) , next while combining the results back again, we need to compare the results produced from two sub problems, 1 comparision for max element and other comparision for min element..

0

if you take a small example and see, for example 6 elements, you will notice it takes 2*(n-1) = 2*5 = 10 comparisons. Which is the same as linear approach. But the recurrence relation approximates some values. Example T(5) = 2T(2) + 2. Instead of T(3) + T(2) + 2

Let me explain this in detail. Consider 6 elements

T(6) = 2T(3) + 2

= 2(T(2) + T(1) + 2) + 2

= 2 (2 + 0 + 2) + 2

= 2*4 + 2

= 10

But due to approximations in when we computes T(n) = 3n/2 -2

we get T(6) as 3*6/2 -2 = 7.

Hence actual answer will be 2*(n-1) for 100 elements, which is 198 instead of 148.

Let me explain this in detail. Consider 6 elements

T(6) = 2T(3) + 2

= 2(T(2) + T(1) + 2) + 2

= 2 (2 + 0 + 2) + 2

= 2*4 + 2

= 10

But due to approximations in when we computes T(n) = 3n/2 -2

we get T(6) as 3*6/2 -2 = 7.

Hence actual answer will be 2*(n-1) for 100 elements, which is 198 instead of 148.

0

@arjun Can we use extra O(logn) memory here?If yes then the answer should be n + ceil(logn) - 2 considering we keep track of the nodes that lose to the smallest element which will be at max logn.

0

@Hcas Hgnis

The maximum number of comparisons in your code will be (2n-2).

So, the average number of comparisons will be

[(n-1)+(2n-2)]/2

(3n-3)/2

1.5(n-1)

1.5(99)

149

Can we solve this like that?

The maximum number of comparisons in your code will be (2n-2).

So, the average number of comparisons will be

[(n-1)+(2n-2)]/2

(3n-3)/2

1.5(n-1)

1.5(99)

149

Can we solve this like that?

0

If number are already sorted then why do we even need comparison.We can directly say first element is min while last is max?

+1

@akshay7797 see this link I was also confused in solving this recurrence relation

https://math.stackexchange.com/questions/2829507/solve-the-recurrence-tn-2-tn-2-2

+37 votes

**Tournament Method Technique(Easy Method by example)**

For example we have 8 elements [1,4,5,8,3,2,7,9]

Step-1: Make buckets of **2** elements:: (1,4) (5,8) (3,2) (7,9)

Step-2: Find **Minimum **and **Maximum** from this buckets, and make** both side expanding tree** like this,

Step-3: So you need** (n-1) **comparisons for finding either **minimum or maximum**

Step-4: first **(n/2) **comparisons only needed once.

Step-5: So total(**Minimum+Maximum**): **2*(n-1)-(n/2) = [3*(n/2)-2]**

+21 votes

**NOTE:** At** level 1** in $\frac{n}{2}$ comparisons we are finding Both MINIMUM as well as MAXIMUM for

Let's see for minimum,

At level 1 :$\frac{n}{2}$ comparisons

At level 2 : $\frac{n}{2^2}$ comparisons

At level 3 : $\frac{n}{2^3}$ comparisons

so on....

At level logn : $\frac{n}{2^{logn}}$ comparisons

So, Total number of comparisons will be

$\frac{n}{2}$ + $\frac{n}{2^2}$ + $\frac{n}{2^3}$ + .....+ $\frac{n}{2^{logn}}$

$\Rightarrow$ n ($\frac{1}{2}$ + $\frac{1}{2^2}$ + $\frac{1}{2^3}$ + .....+ $\frac{1}{2^{logn}}$ ) [apply Sum of G.P]

$\Rightarrow$ $n\frac{1}{2}(\frac{1-(\frac{1}{2})^{logn}}{1-\frac{1}{2}})$

$\Rightarrow$ $n\frac{1}{2}(\frac{1-(2)^{-logn}}{\frac{1}{2}})$

$\Rightarrow$ $n(1-\frac{1}{n})$

$\Rightarrow$ $n-1$

So,total comparisons required to find minimum of n element is **n-1** comparisons.

similarly for Max **n-1** comparisons required.

So total comparisons for both min and max will be

$2(n-1) - \frac{n}{2}$ $\Rightarrow$ $\frac{3n}{2}-2$

[ $\frac{n}{2}$ is reduced because at Level 1 we have taken $\frac{n}{2}$ for both while min and max calculation ]

coming to question n = 100,

total comparisons $\Rightarrow$ $\frac{3 * 100}{2}-2 = 148$

+11 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

+7 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.

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.

+5 votes

for more methods you can refer to http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array

+5 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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,167 answers

193,838 comments

94,017 users