Dada una array A desordenada de tamaño N , la tarea es encontrar los valores mínimo y máximo que se pueden calcular sumando exactamente N-1 elementos.
Ejemplos:
Entrada: a[] = {13, 5, 11, 9, 7}
Salida: 32 40
Explicación: La suma mínima es 5 + 7 + 9 + 11 = 32 y la suma máxima es 7 + 9 + 11 + 13 = 40.
Entrada : a[] = {13, 11, 45, 32, 89, 21}
Salida: 122 200
Explicación: La suma mínima es 11 + 13 + 21 + 32 + 45 = 122 y la suma máxima es 13 + 21 + 32 + 45 + 89 = 200.
Entrada: a[] = {6, 3, 15, 27, 9}
Salida: 33 57
Explicación: La suma mínima es 3 + 6 + 9 + 15 = 33 y la suma máxima es 6 + 9 + 15 + 27 = 57.
Enfoque sencillo:
- Ordene la array en orden ascendente.
- La suma de los primeros N-1 elementos de la array da la suma mínima posible.
- La suma de los últimos N-1 elementos de la array da la suma máxima posible.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
35 40 1000 1400
Complejidad del tiempo: O(NlogN)
Enfoque eficiente:
- Encuentre el elemento mínimo y máximo de la array.
- Calcular la suma de todos los elementos de la array.
- Si se excluye el elemento máximo de la suma, se obtiene la suma mínima posible.
- Si se excluye el elemento mínimo de la suma, se obtiene la suma máxima posible.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
32 40 122 200 33 57
Complejidad del tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por prashant_srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA