# Sum Of Max And Min

Posted: 7 Jan, 2021

Difficulty: Easy

#### 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

Approach 2

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

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:- 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

# Connecting Ropes

Posted: 12 Nov, 2021

Difficulty: Hard

# Insertion Sort

Posted: 30 Nov, 2021

Difficulty: Easy

# Subarrays With Zero Sum

Posted: 1 Dec, 2021

Difficulty: Easy

# Find Student

Posted: 1 Dec, 2021

Difficulty: Easy

# Smaller Than Triplet Sum

Posted: 1 Dec, 2021

Difficulty: Moderate