Sum Of Max And Min

PROBLEM STATEMENT

You are given an array “ARR” of size N. Your task is to find out the sum of maximum and minimum elements in the array.

Follow Up:

Can you do the above task in a minimum number of comparisons?

Input format:

The first line of input contains a single integer T, representing the number of test cases.
Then the T test cases follow. 

The first line of each test case contains a single integer N representing the size of the array 'ARR'.

The second line of each test case contains N space separated integers representing the elements of the array “arr”.

Output format:

For each test case, print the sum of the maximum and minimum element of the array 'ARR'.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^5 
-10^9 <= ARR[i] <= 10^9

Time limit: 1 second

Approach 1

Sort the array so that the 0th element will be the minimum value of the array and the last element will be the maximum value present in out array.

Try Problem

Approach 2

Steps:

Create two variables maximum and minimum, and initialise with arr[0].
Run a loop from i = 1 to N-1 and do:
1. If arr[i] > maximum, then make maximum = arr[i].
2. Else If arr[i] < minimum, then make minimum = arr[i].
Note that, the above step, takes 2 * (N - 1) comparisons in the worst case when the array is sorted in decreasing order.
At last return maximum + minimum.

Try Problem

Approach 3

The idea is to use a divide and conquer approach in order to reduce the number of comparisons. We divide the array into two equal parts and find the maximum and minimum element of each part recursively. Then we compare the maximum and minimum of both parts in order to find the maximum and minimum element of the whole array.

Steps:

Create a data type that contains two integers as maximum and minimum. The first integer denotes the maximum value whereas the second one denotes the minimum value. Let’s denote the name of this variable as maxMin.
Implement a recursive function say findMaxMin(arr, 0, N-1).
Finally, return the sum of maximum and minimum.

pair<int, int> findMaxMin(arr, left, right):

If left == right, i.e. only one element is present in the array, then return {arr[left], arr[right]}.
If right == left + 1, i.e. only two elements are present in the array, then:
1. If arr[left] > arr[right], then return {arr[left], arr[right]}.
2. Else, return {arr[right], arr[left]}.
Create a mid variable and make mid = (left + right) / 2.
Create two more pairs of integers, say leftAns and rightAns in order to store the result of the left half and right half respectively.
Call the recursive function from left to mid for the leftAns and mid + 1 to right for the rightAns, i.e. leftAns = findMaxMin(arr, left, mid) and rightAns = findMaxMin(arr, mid+1, right).
Finally, return the maximum among the maximum of leftAns and rightAns and minimum among the minimum of leftAns and rightAns i.e. {max(leftAns.first, rightAns.first), min(leftAns.second, rightAns.second)}.