## Median of 2 sorted arrays of equal lengths

#include <iostream> using namespace std; int median(int a[],int n) { if(n%2==0) { return (a[n/2]+a[n/2-1])/2; } else { return a[n/2]; } } int getMedian(int a[],int b[],int n) { if(n==0) { return 0; } else if(n==1) { return (a[0]+b[0])/2; } else if(n==2) { return (max(a[0],b[0])+min(a[1],b[1]))/2; } int m1 = median(a,n); int m2 = median(b,n); if(m1==m2) { return m1; } else if(m1<m2) { return getMedian(a+n/2,b,n-n/2); } else { return getMedian(a,b+n/2,n-n/2); } } int main() { int ar1[] = {1, 12, 15, 26, 38}; int ar2[] = {2, 13, 17, 30, 45}; cout<<getMedian(ar1, ar2, 5); return 0; }

## 25 Horses

**Problem**: Letâ€™s say that you have 25 horses, and you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?

**Solution:**

7 races should do the job. Lets assume a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2, c3, c4, c5, d1, d2, d3, d4, d5, e1, e2, e3, e4, e5 are the horses belonging to five groups a, b, c, d, e.

First race all 5 individual groups: 5 races

Now assume a1, a2, a3, b1-b3, c1-c3, d1-d3, e1-e3 are the top 3 in each group in the same order(a1 – fastest).

Now race a1, b1, c1, d1 and e1 – 1 race -> this should give us the fastest horse in all. Assume a1 – is fastest. Eliminate a1 from the group. Next assume b1 – 2nd, c1- 3rd, d1- 4th, e1- 5th in this race. So this eliminates d1, e1 and d2,d3,e2,e3 from the race.

Now we need to race a2,a3,b1,b2,c1 – last race. Here the top two horses would be second and third respectively.

So 7 races will do.