Dada una array arr[] de N elementos. En cualquier paso, podemos eliminar un número de paridad diferente del paso anterior, es decir, si en el paso anterior se eliminó un número impar, en el paso actual se elimina un número par o viceversa.
Se permite comenzar borrando cualquier número. La eliminación es posible hasta que podamos eliminar números de diferente paridad en cada paso. La tarea es encontrar la suma mínima posible de los elementos que quedan al final.
Ejemplos:
Entrada: arr[] = {1, 5, 7, 8, 2}
Salida: 0
Elimina elementos en el orden 1, 2, 5, 8 y finalmente 7.
Hay múltiples formas de eliminación,
lo que da como resultado la misma suma minimizada.Entrada: arr[] = {2, 2, 2, 2}
Salida: 6
Eliminar 2 en el primer paso.
No se puede borrar ningún número, ya que no quedan números impares.
Por lo tanto, la suma de los elementos sobrantes es 6.
Enfoque: Se pueden seguir las siguientes formas para resolver el problema anterior:
- Cuente el número de elementos pares e impares y almacénelos en los vectores v1 y v2 .
- Compruebe si el número de elementos pares e impares es el mismo o difiere en 1 , luego podemos realizar N pasos, lo que da como resultado una suma sobrante de 0.
- Si el tamaño difiere en más de 1, solo habrá elementos sobrantes.
- Para minimizar la suma sobrante de elementos, seleccionamos primero los elementos más grandes.
- Por lo tanto, la suma de los X elementos más pequeños será la respuesta, donde X es v2.size() – v1.size() – 1 o v1.size() – v2.size() – 1 dependiendo del conteo de pares y elementos extraños.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimized sum
int MinimizeleftOverSum(int a[], int n)
{
vector<int> v1, v2;
for (int i = 0; i < n; i++) {
if (a[i] % 2)
v1.push_back(a[i]);
else
v2.push_back(a[i]);
}
// If more odd elements
if (v1.size() > v2.size()) {
// Sort the elements
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
// Left-over elements
int x = v1.size() - v2.size() - 1;
int sum = 0;
int i = 0;
// Find the sum of leftover elements
while (i < x) {
sum += v1[i++];
}
// Return the sum
return sum;
}
// If more even elements
else if (v2.size() > v1.size()) {
// Sort the elements
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
// Left-over elements
int x = v2.size() - v1.size() - 1;
int sum = 0;
int i = 0;
// Find the sum of leftover elements
while (i < x) {
sum += v2[i++];
}
// Return the sum
return sum;
}
// If same elements
else
return 0;
}
// Driver code
int main()
{
int a[] = { 2, 2, 2, 2 };
int n = sizeof(a) / sizeof(a[0]);
cout << MinimizeleftOverSum(a, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to find the minimized sum
static int MinimizeleftOverSum(int a[], int n)
{
Vector<Integer> v1 = new Vector<Integer>(),
v2 = new Vector<Integer>();
for (int i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
v1.add(a[i]);
else
v2.add(a[i]);
}
// If more odd elements
if (v1.size() > v2.size())
{
// Sort the elements
Collections.sort(v1);
Collections.sort(v2);
// Left-over elements
int x = v1.size() - v2.size() - 1;
int sum = 0;
int i = 0;
// Find the sum of leftover elements
while (i < x)
{
sum += v1.get(i++);
}
// Return the sum
return sum;
}
// If more even elements
else if (v2.size() > v1.size())
{
// Sort the elements
Collections.sort(v1);
Collections.sort(v2);
// Left-over elements
int x = v2.size() - v1.size() - 1;
int sum = 0;
int i = 0;
// Find the sum of leftover elements
while (i < x)
{
sum += v2.get(i++);
}
// Return the sum
return sum;
}
// If same elements
else
return 0;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 2, 2, 2 };
int n = a.length;
System.out.println(MinimizeleftOverSum(a, n));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # Function to find the minimized sum def MinimizeleftOverSum(a, n) : v1, v2 = [], []; for i in range(n) : if (a[i] % 2) : v1.append(a[i]); else : v2.append(a[i]); # If more odd elements if (len(v1) > len(v2)) : # Sort the elements v1.sort(); v2.sort(); # Left-over elements x = len(v1) - len(v2) - 1; sum = 0; i = 0; # Find the sum of leftover elements while (i < x) : sum += v1[i]; i += 1 # Return the sum return sum; # If more even elements elif (len(v2) > len(v1)) : # Sort the elements v1.sort(); v2.sort(); # Left-over elements x = len(v2) - len(v1) - 1; sum = 0; i = 0; # Find the sum of leftover elements while (i < x) : sum += v2[i]; i += 1 # Return the sum return sum; # If same elements else : return 0; # Driver code if __name__ == "__main__" : a = [ 2, 2, 2, 2 ]; n = len(a); print(MinimizeleftOverSum(a, n)); # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimized sum
static int MinimizeleftOverSum(int []a,
int n)
{
List<int> v1 = new List<int>(),
v2 = new List<int>();
for (int i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
v1.Add(a[i]);
else
v2.Add(a[i]);
}
// If more odd elements
if (v1.Count > v2.Count)
{
// Sort the elements
v1.Sort();
v2.Sort();
// Left-over elements
int x = v1.Count - v2.Count - 1;
int sum = 0;
int i = 0;
// Find the sum of leftover elements
while (i < x)
{
sum += v1[i++];
}
// Return the sum
return sum;
}
// If more even elements
else if (v2.Count > v1.Count)
{
// Sort the elements
v1.Sort();
v2.Sort();
// Left-over elements
int x = v2.Count - v1.Count - 1;
int sum = 0;
int i = 0;
// Find the sum of leftover elements
while (i < x)
{
sum += v2[i++];
}
// Return the sum
return sum;
}
// If same elements
else
return 0;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 2, 2, 2, 2 };
int n = a.Length;
Console.WriteLine(MinimizeleftOverSum(a, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript implementation of the approach
// Function to find the minimized sum
function MinimizeleftOverSum(a , n)
{
var v1 = [], v2 =[];
for (i = 0; i < n; i++)
{
if (a[i] % 2 == 1)
v1.push(a[i]);
else
v2.push(a[i]);
}
// If more odd elements
if (v1.length > v2.length)
{
// Sort the elements
v1.sort();
v2.sort();
// Left-over elements
var x = v1.length - v2.length - 1;
var sum = 0;
var i = 0;
// Find the sum of leftover elements
while (i < x)
{
sum += v1[i++];
}
// Return the sum
return sum;
}
// If more even elements
else if (v2.length > v1.length)
{
// Sort the elements
v1.sort();
v2.sort();
// Left-over elements
var x = v2.length - v1.length - 1;
var sum = 0;
var i = 0;
// Find the sum of leftover elements
while (i < x)
{
sum += v2[i++];
}
// Return the sum
return sum;
}
// If same elements
else
return 0;
}
// Driver code
var a = [ 2, 2, 2, 2 ];
var n = a.length;
document.write(MinimizeleftOverSum(a, n));
// This code is contributed by Rajput-Ji
</script>
Producción:
6
Complejidad de tiempo: O (n * log n), ya que en el peor de los casos usaremos una función de ordenación incorporada para ordenar una array de tamaño n. Donde N es el número de elementos de la array.
Espacio auxiliar: O(n), ya que estamos usando espacio adicional para la array v1 y v2. Donde N es el número de elementos de la array.