Find the minimum and maximum sum of N-1 elements of the array
Given an unsorted array A of size N, the task is to find the minimum and maximum values that can be calculated by adding exactly N-1 elements.
Examples:
Input: a[] = {13, 5, 11, 9, 7}
Output: 32 40
Explanation: Minimum sum is 5 + 7 + 9 + 11 = 32 and maximum sum is 7 + 9 + 11 + 13 = 40.
Input: a[] = {13, 11, 45, 32, 89, 21}
Output: 122 200
Explanation: Minimum sum is 11 + 13 + 21 + 32 + 45 = 122 and maximum sum is 13 + 21 + 32 + 45 + 89 = 200.
Input: a[] = {6, 3, 15, 27, 9}
Output: 33 57
Explanation: Minimum sum is 3 + 6 + 9 + 15 = 33 and maximum sum is 6 + 9 + 15 + 27 = 57.
Simple Approach:
- Sort the array in ascending order.
- Sum of the first N-1 elements in the array gives the minimum possible sum.
- Sum of the last N-1 elements in the array gives the maximum possible sum.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h> using namespace std; // Python Implementation of the above approach void minMax(vector< int >&arr){ // Initialize the min_value // and max_value to 0 int min_value = 0; int max_value = 0; int n = arr.size(); // Sort array before calculating // min and max value sort(arr.begin(),arr.end()); int j = n - 1; for ( int i = 0; i < n - 1; i++) { // All elements except // rightmost will be added min_value += arr[i]; // All elements except // leftmost will be added max_value += arr[j]; j -= 1; } // Output: min_value and max_value cout<<min_value<< " " <<max_value<<endl; } // Driver Code int main(){ vector< int >arr = {10, 9, 8, 7, 6, 5}; vector< int >arr1 = {100, 200, 300, 400, 500}; minMax(arr); minMax(arr1); } // This code is contributed by shinjanpatra |
Java
// Java Implementation of the above approach import java.util.*; class GFG { static void minMax( int [] arr) { // Initialize the min_value // and max_value to 0 long min_value = 0 ; long max_value = 0 ; int n = arr.length; // Sort array before calculating // min and max value Arrays.sort(arr); for ( int i = 0 , j = n - 1 ; i < n - 1 ; i++, j--) { // All elements except // rightmost will be added min_value += arr[i]; // All elements except // leftmost will be added max_value += arr[j]; } // Output: min_value and max_value System.out.println( min_value + " " + max_value); } // Driver Code public static void main(String[] args) { Scanner sc = new Scanner(System.in); // Initialize your array elements here int [] arr = { 10 , 9 , 8 , 7 , 6 , 5 }; int [] arr1 = { 100 , 200 , 300 , 400 , 500 }; minMax(arr); minMax(arr1); } } |
Python3
# Python Implementation of the above approach def minMax(arr): # Initialize the min_value # and max_value to 0 min_value = 0 max_value = 0 n = len (arr) # Sort array before calculating # min and max value arr.sort() j = n - 1 for i in range (n - 1 ): # All elements except # rightmost will be added min_value + = arr[i] # All elements except # leftmost will be added max_value + = arr[j] j - = 1 # Output: min_value and max_value print (min_value, " " ,max_value) # Driver Code arr = [ 10 , 9 , 8 , 7 , 6 , 5 ] arr1 = [ 100 , 200 , 300 , 400 , 500 ] minMax(arr) minMax(arr1) # This code is contributed by ab2127. |
C#
using System; public class GFG{ static void minMax( int [] arr) { // Initialize the min_value // and max_value to 0 long min_value = 0; long max_value = 0; int n = arr.Length; // Sort array before calculating // min and max value Array.Sort(arr); int j = n - 1; for ( int i = 0 ;i < n - 1; i++) { // All elements except // rightmost will be added min_value += arr[i]; // All elements except // leftmost will be added max_value += arr[j]; j--; } // Output: min_value and max_value Console.WriteLine( min_value + " " + max_value); } // Driver Code static public void Main (){ // Initialize your array elements here int [] arr = { 10, 9, 8, 7, 6, 5 }; int [] arr1 = { 100, 200, 300, 400, 500 }; minMax(arr); minMax(arr1); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript Implementation of the above approach function minMax(arr) { // Initialize the min_value // and max_value to 0 let min_value = 0; let max_value = 0; let n = arr.length; // Sort array before calculating // min and max value arr.sort( function (a,b){ return a-b;}); for (let i = 0, j = n - 1; i < n - 1; i++, j--) { // All elements except // rightmost will be added min_value += arr[i]; // All elements except // leftmost will be added max_value += arr[j]; } // Output: min_value and max_value document.write( min_value + " " + max_value+ "<br>" ); } // Driver Code let arr=[10, 9, 8, 7, 6, 5]; let arr1=[100, 200, 300, 400, 500 ]; minMax(arr); minMax(arr1); // This code is contributed by avanitrachhadiya2155 </script> |
Output:
35 40 1000 1400
Time complexity: O(NlogN)
Auxiliary Space: O(1), As constant extra space is used.
Efficient Approach:
- Find the minimum and maximum element of the array.
- Calculate the sum of all the elements in the array.
- Excluding maximum element from the sum gives the minimum possible sum.
- Excluding the minimum element from the sum gives the maximum possible sum.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum and maximum // sum from an array. #include <bits/stdc++.h> using namespace std; // Function to calculate minimum and maximum sum static void miniMaxSum( int arr[], int n) { // Initialize the minElement, maxElement // and sum by 0. int minElement = 0, maxElement = 0, sum = 0; // Assigning maxElement, minElement // and sum as the first array element minElement = arr[0]; maxElement = minElement; sum = minElement; // Traverse the entire array for ( int i = 1; i < n; i++) { // Calculate the sum of // array elements sum += arr[i]; // Keep updating the // minimum element if (arr[i] < minElement) { minElement = arr[i]; } // Keep updating the // maximum element if (arr[i] > maxElement) { maxElement = arr[i]; } } // print the minimum and maximum sum cout << (sum - maxElement) << " " << (sum - minElement) << endl; } // Driver Code int main() { // Test Case 1: int a1[] = { 13, 5, 11, 9, 7 }; int n = sizeof (a1) / sizeof (a1[0]); // Call miniMaxSum() miniMaxSum(a1, n); // Test Case 2: int a2[] = { 13, 11, 45, 32, 89, 21 }; n = sizeof (a2) / sizeof (a2[0]); miniMaxSum(a2, n); // Test Case 3: int a3[] = { 6, 3, 15, 27, 9 }; n = sizeof (a3) / sizeof (a3[0]); miniMaxSum(a3, n); } // This code is contributed by chitranayal |
Java
// Java program to find the minimum and maximum // sum from an array. class GFG { // Function to calculate minimum and maximum sum static void miniMaxSum( int [] arr) { // Initialize the minElement, maxElement // and sum by 0. int minElement = 0 , maxElement = 0 , sum = 0 ; // Assigning maxElement, minElement // and sum as the first array element minElement = arr[ 0 ]; maxElement = minElement; sum = minElement; // Traverse the entire array for ( int i = 1 ; i < arr.length; i++) { // calculate the sum of // array elements sum += arr[i]; // Keep updating the // minimum element if (arr[i] < minElement) { minElement = arr[i]; } // Keep updating the // maximum element if (arr[i] > maxElement) { maxElement = arr[i]; } } // print the minimum and maximum sum System.out.println((sum - maxElement) + " " + (sum - minElement)); } // Driver Code public static void main(String args[]) { // Test Case 1: int a1[] = { 13 , 5 , 11 , 9 , 7 }; // Call miniMaxSum() miniMaxSum(a1); // Test Case 2: int a2[] = { 13 , 11 , 45 , 32 , 89 , 21 }; miniMaxSum(a2); // Test Case 3: int a3[] = { 6 , 3 , 15 , 27 , 9 }; miniMaxSum(a3); } } |
Python3
# Python3 program to find the minimum and # maximum sum from a list. # Function to calculate minimum and maximum sum def miniMaxSum(arr, n): # Initialize the minElement, maxElement # and sum by 0. minElement = 0 maxElement = 0 sum = 0 # Assigning maxElement, minElement # and sum as the first list element minElement = arr[ 0 ] maxElement = minElement sum = minElement # Traverse the entire list for i in range ( 1 , n): # Calculate the sum of # list elements sum + = arr[i] # Keep updating the # minimum element if (arr[i] < minElement): minElement = arr[i] # Keep updating the # maximum element if (arr[i] > maxElement): maxElement = arr[i] # Print the minimum and maximum sum print ( sum - maxElement, sum - minElement) # Driver Code # Test Case 1: a1 = [ 13 , 5 , 11 , 9 , 7 ] n = len (a1) # Call miniMaxSum() miniMaxSum(a1, n) # Test Case 2: a2 = [ 13 , 11 , 45 , 32 , 89 , 21 ] n = len (a2) miniMaxSum(a2, n) # Test Case 3: a3 = [ 6 , 3 , 15 , 27 , 9 ] n = len (a3) miniMaxSum(a3, n) # This code is contributed by vishu2908 |
C#
// C# program to find the minimum and maximum // sum from an array. using System; class GFG{ // Function to calculate minimum and maximum sum static void miniMaxSum( int [] arr) { // Initialize the minElement, maxElement // and sum by 0. int minElement = 0, maxElement = 0, sum = 0; // Assigning maxElement, minElement // and sum as the first array element minElement = arr[0]; maxElement = minElement; sum = minElement; // Traverse the entire array for ( int i = 1; i < arr.Length; i++) { // Calculate the sum of // array elements sum += arr[i]; // Keep updating the // minimum element if (arr[i] < minElement) { minElement = arr[i]; } // Keep updating the // maximum element if (arr[i] > maxElement) { maxElement = arr[i]; } } // Print the minimum and maximum sum Console.WriteLine((sum - maxElement) + " " + (sum - minElement)); } // Driver Code public static void Main() { // Test Case 1: int [] a1 = new int []{ 13, 5, 11, 9, 7 }; // Call miniMaxSum() miniMaxSum(a1); // Test Case 2: int [] a2 = new int []{ 13, 11, 45, 32, 89, 21 }; miniMaxSum(a2); // Test Case 3: int [] a3 = new int []{ 6, 3, 15, 27, 9 }; miniMaxSum(a3); } } // This code is contributed by sanjoy_62 |
Javascript
<script> // Function to calculate minimum and maximum sum function miniMaxSum( arr, n) { // Initialize the minElement, maxElement // and sum by 0. var minElement = 0, maxElement = 0, sum = 0; // Assigning maxElement, minElement // and sum as the first array element minElement = arr[0]; maxElement = minElement; sum = minElement; // Traverse the entire array for ( var i = 1; i < n; i++) { // Calculate the sum of // array elements sum += arr[i]; // Keep updating the // minimum element if (arr[i] < minElement) { minElement = arr[i]; } // Keep updating the // maximum element if (arr[i] > maxElement) { maxElement = arr[i]; } } // print the minimum and maximum sum document.write((sum - maxElement)+ " " + (sum - minElement) + "<br>" ); } // Driver Code var a1= [ 13, 5, 11, 9, 7 ]; // Call miniMaxSum() miniMaxSum(a1, 5); // Test Case 2: var a2 = [13, 11, 45, 32, 89, 21 ]; miniMaxSum(a2, 6); // Test Case 3: var a3 = [ 6, 3, 15, 27, 9 ]; miniMaxSum(a3, 5); </script> |
32 40 122 200 33 57
Time complexity: O(N)
Auxiliary Space: O(1), As constant extra space is used.