(5 votes, average: 4.40 out of 5)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
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
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
32 “SORTED” numbers.
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.
jjjjjj
47
61
It’s just 35
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 )
We wanted total comparisons done, here we are doing way more than 35..(look for all comparisons)
Hey Ganesh just check the nunber of times the if and else if conditions r being checked… Its 2(n-1).
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.
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 ?
16
8
4
2
1
So the total is 31… and thats the answer
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.
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.
its for second highest number, not the first one
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 🙂
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.
35
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)
32 should be the answer