CareerCup

to find first and second minimum we need 4 comparison
consider 5 4 1 2 3
(5,4) ,(4,1) ,(4,2), (4,3)
for third element
compare (1,2)->swap
compare(2,3)->swap

6 comparison

Yes it would be 6 comparison ...

We would need 4.
For a list of size n, we would need at least n-1 comparisons.
Every element has to be compared at least once, nothing better than this can exist.
If we use quick sort until we end up with pivot as the median element the complexity on average would be O(n).

we can do it in 4 comparision

if a[0]>a[2] swap them
if a[4]>a[2] swap them
if a[1]>a[2] swap them
if a[3]>a[2] swap them

a[2] is the median

Doesn't it depend on order of input? It can vary accordingly.

are comparisons the only operation allowed ?
what if we first add all the elements and divide by the no. of elements,
and then compare it with all the elements to find the one closest to the absolute value
e.g.

// dummy code

int median = -1, diff = -1;
int mid = ( arr[0]+arr[1]+arr[2]+arr[3]+arr[4] )/5;

median = 0;
diff = abs(mid - arr[0]);
for(int i =1;i<5;i++)
{
      if( abs(mid-arr[i]) < diff )
      {
             diff = abs(mid - arr[i])
             median = 0;
      }
}

so that should count for 5 comparisons, but the total no. of accesses would be 10

It will need 6 comparisons.
1. First make the array such that a[1] < a[2], a[4] < a[5] and a[1] < a[4].
a. compare a[1] and a[2]. swap if necessary.
b. compare a[4] and a[5]. swap if necessary.
c. compare a[1] and a[4]. if a[4] is smaller than a[1] then swap a[1] with a[4] and s[2] with a[5].
2. if a[3] > a[2]. if a[2] > a[4], median = min(a[2], a[5]) else median = min(a[3], a[4]).
3. if a[3] < a[2]. if a[3] > a[4], median = min(a[3], a[5]) else median = min(a[2], a[4]).

So in total 6 comparisons.
To extend it for a list of size n, use select algorithm (media of medians algorithm).

how much will take for 7 elements? 9 or 16? can any tell ?

We can do it in 4 comparision.

Logic is to find: First largest element -> Second Largest element ->Third Largest Element.

Third Largest element will be median, if there are 5 unsorted elements in array.

void Median() {

int a[] = {4,5,2,3,1};
int larg, secLarg, i, Median;
int len = (sizeof(a)/sizeof a[0]);

larg = a[0]; secLarg = a[1], Median = a[2];

for(i=1; i < len; i++) {

if(larg > a[i]) {
if (secLarg < a[i]) {
secLarg = a[i];
}
if(Median < a[i] && Median <= secLarg && i>2)
Median = a[i];
}
else {
secLarg = larg;
larg = a[i];
if(Median < a[i] && Median <= secLarg && i>2)
Median = a[i];
}
}

cout << "Median is :" << Median << endl;
}

4.
Test cases.
( 1 3 5 7 6), ( 1 6 7 5 2). To find median is possible in O(n) time complexity with space complexity O(1)

I think the question is a little bit weird...
now, consider an example with 3 numbers: a0, a1, a2
step 1:
we compare a0 and a1. result a0<a1

step 2:
we compare a1 and a2. result a1<a2 (yet we cannot guarantee it)

in this specific case, the number of comparison is 2, we have a0<a1<a2, so median is a1.

I think this is the minimum comparison number. Yet we need the number sequence satisfies some conditions.

We still use the previous example. If a1>a2. We would not know which one is median. So we need to compare a0 and a2 again.

For this case, the number of comparison would be 3. But this is worst case.


Basically, for n number , we need to do at least n-1 comparisons to find the median if data sequence satisfies some conditions.

So if we have 5 numbers, we need 4 comparison times.

Please correct me if I am wrong...

The best I can comeup with is 7.
- Need three to get three elements in order: x1  x2  x3
- Now need three more to order x2   x4   x5
- If x4 and x5 fall on either sides of x2 then x2 is median
- If x4 and x5 fall on the same side of x2 (both are greater or smaller then x2) then compare x4 (the element which is closer to x2) with x1 (if x4 is less than x2) or x3 (if x4 is greater than x2)

I think the answer is 8

find the first and second minimum number in 5 numbers,I think need 6 comparison
then find the biggest number in the left 3 numbers,need 2 comparison

first of all, sort the given array with selection sort because selection sort do less no of comparision for sorting and then pick the mid elements of the array which is the median....
in worst case,selection sort compares n-1 elements..hence in this case n=5 so ans is 4 comparision required....

If n is odd then the median is x[(n-1)/2].
If n is even than the median is ( x[n/2] + x[(n/2)-1] ) / 2
so there might not be a need to compare any values so minimum comparisons are 0.