Sum of Maximum and Minimum Elements Problem Statement

Given an array ARR of size N, your objective is to determine the sum of the largest and smallest elements within the array.

Follow Up:

Can you achieve the above task using the least number of comparisons possible?

Input:

The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer N, representing the size of the array ARR. The second line contains N space-separated integers, which are the elements of array ARR.

Output:

For each test case, output the sum of the maximum and minimum elements in the array ARR.

Example:

Input:

2 5 1 3 5 7 9 4 -10 4 7 19

Output:

10 9

Explanation:

In the first test case, the maximum is 9 and the minimum is 1. Their sum is 10.
In the second test case, the maximum is 19 and the minimum is -10. Their sum is 9.

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 10^5

-10^9 ≤ ARR[i] ≤ 10^9

Note:

You are not required to print anything; the function should handle processing the results.

Question

Sum of Maximum and Minimum Elements Problem Statement

Given an array ARR of size N, your objective is to determine the sum of the largest and smallest elements within the array.

Follow Up:

Can you achieve the above task using the least number of comparisons possible?

Input:

The first line contains an integer T, the number of test cases.
For each test case, the first line contains an integer N, representing the size of the array ARR.
The second line contains N space-separated integers, which are the elements of array ARR.

Output:

For each test case, output the sum of the maximum and minimum elements in the array ARR.

Example:

Input:

Output:

10
9

Explanation:

In the first test case, the maximum is 9 and the minimum is 1. Their sum is 10.
In the second test case, the maximum is 19 and the minimum is -10. Their sum is 9.

Constraints:

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

Note:

You are not required to print anything; the function should handle processing the results.

Accepted Answer

Divide and Conquer
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]}.
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)}.
Space Complexity: O(logn)Explanation:
O(log N), where N is the size of the given array.
 
In the worst case, the number of recursive calls can go up to log N. Hence, the overall space complexity is O(log N).
Time Complexity: O(n)Explanation:
O(N), where N is the size of the given array.
 
In the worst case, we will be traversing the whole array, hence the time complexity is O(N).
The number of comparisons can be calculated by the recurrence relation,
T(N) = T(floor(N / 2)) + T(Ceil(N / 2)) + 2
T(1) = 0, T(2) = 1
So, if N is a power of 2, we can represent T(N) = 2T(N / 2) + 2
So, by solving the above relation, we get T(N) = (3 * N) / 2 - 2
So, if N is a power of 2, then the total number of comparisons is (3 * N) / 2 - 2 and if it is not a power of 2, then it will take a few more comparisons, but the difference is not so significant.

Accepted Answer

SortingSort 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.Space Complexity: O(1)Explanation: O(1) In...

Accepted Answer

First I initialized two variables max and min.
and traverse the array to find max and min.
then return the sum of max and min.

Accepted Answer

oo full form is object oriented.