New update is available. Click here to update.

Last Updated: 7 Jan, 2021

Difficulty: Easy

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

```
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”.
```

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

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

```
1 <= T <= 10
1 <= N <= 10^5
-10^9 <= ARR[i] <= 10^9
Time limit: 1 second
```

**Steps:**

- Create two variables
**maximum**and**minimum, and**initialise**arr[0].** - Run a loop from
**i**= 1 to**N-1**and do:- If
**arr[i]**>**maximum**, then make**maximum**=**arr[i]**. - Else If
**arr[i]**<**minimum**, then make**minimum**=**arr[i]**.

- If
- 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**.

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:- If
**arr[left]**>**arr[right]**, then return {**arr[left]**,**arr[right]**}. - Else, return {
**arr[right]**,**arr[left]**}.

- If
- 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**)}.

SIMILAR PROBLEMS

Missing Number

Posted: 30 Oct, 2022

Difficulty: Easy

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

Popular Interview Problems: