Sum Of Max And Min
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

Question

Sum Of Max And Min

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

Accepted Answer

This can be solved by simply traversing the array once and updating the max and min by comparing it with every element. Steps :
1. Initialize min and max with the value of the first element of the array
2. Run a loop from index 1 to n-1 :
For every element, compare it with max and min. Update max and min accordingly.
This approach has O(n) time complexity and O(1) auxiliary space.

Accepted Answer

Sorting

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.

Space Complexity: O(1)Explanation:

O(1)

In the worst case, a constant space is required.

Time Complexity: O(nlogn)Explanation:

O(N * Log(N)), where N is the size of the given array.

Sorting an array of size 'N' takes O(N * Log(N)) time.

Accepted Answer

Iterating

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.

Space Complexity: O(1)Explanation:

O(1)

In the worst case, a constant space is required.

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 overall complexity will be O(N).

Top SAP Senior Software Developer interview questions & answers

Popular interview questions of Senior Software Developer

Top HR questions asked in SAP Senior Software Developer