**You have 32 numbers. What is the least number of comparison needed to find the 2nd smallest out of them?**

Check your answer:- Click here to See Answers

Minimum number of comparisons required will be n + log(n) -2 = 32 + 5 -2 = 35

We can think of this as a tournament where 32 teams are competing against each other, to get the best team out of n teams we need (n-1) comparisons, by taking two teams at a time and then playing the game between the previous winners, Games will be played in the tree format as below

**How?**We can think of this as a tournament where 32 teams are competing against each other, to get the best team out of n teams we need (n-1) comparisons, by taking two teams at a time and then playing the game between the previous winners, Games will be played in the tree format as below

| | | | | | | | | | | | | | |

Now we need to find the second best team: We can say that second best team must have lost against the winner(as otherwise it will not be second). And Total number of games played by the winner are log(n) (height of the tree).

Now our task reduces to just finding the best team from log(n) teams, which we know can be done in log(n) – 1 times.

So total number of comparisons = n-1 + log(n) -1 = n + log(n) -2.

Solution reference: http://stackoverflow.com/questions/3628718/find-the-2nd-largest-element-in-an-array-with-minimum-of-comparisom

Facebook Comments

Baballa says

32 “SORTED” numbers.

steven k says

Inter change the elements in the array and do 31 iterations to identify the second largest. Using sorting techniques, time complexity goes beyond n. i.e, 32.

jjjjj says

jjjjjj

Gopal Zawar says

47

Praveen Benny says

61

Priyamyolo says

It’s just 35

Ganesh says

pls find the revised solution

int SecondMin = 0;

int Min = 0;

if(arr[0] > arr[1])

{

SecondMin = arr[0];

Min = arr[1];

}

else

{

SecondMin = arr[1];

Min = arr[0];

}

for(int i = 2 ; i < arr.Length -1 ; i++)

{

if ( arr[i] < Min )

{

SecondMin = Min;

Min = arr[i];

}

else if(arr[i] < SecondMin)

{

SecondMin = arr[i];

}

}

it will work in O( N -1 )

puzzlersworld says

We wanted total comparisons done, here we are doing way more than 35..(look for all comparisons)

Sup says

Hey Ganesh just check the nunber of times the if and else if conditions r being checked… Its 2(n-1).

Ganesh says

How about this ?

Imagine arr[] is the array of elements

int SecondMin = arr[0];

int Min = arr[0];

for(int i = 1 ; i < arr.Length ; i++)

{

if ( arr[i] < Min )

{

SecondMin = Min;

Min = arr[i];

}

}

so in the end of the loop i will get my second minimum in 31 comparisons.

puzzlersworld says

There is a boundary case where this will not work(first number is minimum of all)

lets assume the array is

1,2,3,4,5,6,7,8

Now what will your code return as second min ?

manish says

16

8

4

2

1

So the total is 31… and thats the answer

Dimitris Kaka says

We want the second smallest number between 32 numbers. 31 is the correct answer for the Smallest number. In this problem, the right solution is 35.

Mukesh Kumar says

it must be 31.

we can go through divide and conquer and when we have two numbers we find the maximum of them

so the answer will be 31.

puzzlersworld says

its for second highest number, not the first one

Riya says

Even for the binary tree type structure , we need a total of 16+8+4+2+1=31 comparisons , to find the maximum number , once we find that we know the second largest number , so correct answer should b 31 ðŸ™‚

puzzlersworld says

no, lets say out of 16 comparisons, first comparison was among the first and second highest, in that case second highest will not come in next 8 numbers and thus it is not compulsory that the last 2 numbers are first and second highest.

Omer Farooq says

35

Deepak Maurya says

one who loose against the winner is the second winner so no more comparison needed.

To get the winner we are getting 31 comparison same for looser in the final round(2nd winner)

livinggod29.com says

32 should be the answer