medium puzzles
| medium | strategy |
Given an array of n numbers. Finding minimum takes n-1 comparisons. Finding maximum takes n-1 comparisons. If you had to simultaneously find both minimum and maximum, can you do it in less than 2n-2 comparisons?
the answer is ~1.5n calculations. It uses a trick. When you compare two elements, one comparison is sufficient to find both min & max of those two elements.
Solution requires approximately 1.5n comparisons instead of 2n comparisons.
Break n numbers into pairs of 2. So, that is n/2 pairs. Find maximum and minimum in each pair. Cost = n/2. Now given n/2 maximums, find the maximum. Cost = n/2. Given n/2 minimums, find the minimum. Cost = n/2
So, overall cost 3n/2 comparisons.