Diferencia entre la suma de K elementos de array pares e impares máximos

Dada una array arr[] y un número K , la tarea es encontrar la diferencia absoluta de la suma de K elementos de array pares e impares máximos.
Nota: Al menos K elementos pares e impares están presentes en la array respectivamente.

Ejemplos:

Entrada arr[] = {1, 2, 3, 4, 5, 6}, K = 2
Salida: 2
Explicación :
Los 2 números pares máximos son 6, 4. La suma es 6 + 4 = 10.
Los 2 números impares máximos los números son 5, 3. La suma es 5 + 3 = 8.
Diferencia = 10 – 8 = 2.

Entrada arr[] = {1, 8, 4, 5, 6, 3}, K = 3
Salida: 4
Explicación :
Los 3 números pares máximos son 8, 6, 4. La suma es 8 + 6 + 4 = 18.
Los 3 números impares máximos son 5, 3, 1. La suma es 5 + 3 + 1 = 9.
Diferencia = 18 – 9 = 9.

Enfoque ingenuo: el enfoque más simple es encontrar los K números pares máximos y los K números impares máximos recorriendo la array e imprimir la diferencia absoluta entre la suma de los K elementos pares e impares máximos obtenidos. 

Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el concepto de segregar la array en números pares e impares y luego clasificar la array en dos partes en orden descendente que contengan números pares e impares respectivamente. Siga los pasos a continuación para resolver el problema:

• Separe el número par y el número impar en la array dada respectivamente y almacene el índice desde donde comienzan los números impares.
• Sea K el índice de donde parten los números impares . Ordene el número en el rango [0, K – 1] y [K, N – 1] en orden decreciente.
• La suma de los primeros K números desde el comienzo de la array y desde el punto donde comienzan los números impares es la suma de los primeros K números pares e impares máximos en la array, respectivamente.
• Imprime la diferencia absoluta entre las sumas calculadas en el paso anterior como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the absolute
// difference between sum of first K
// maximum even and odd numbers
void evenOddDiff(int a[], int n, int k)
{
    // Stores index from where odd
    // number starts
    int j = -1;
 
    // Segregate even and odd number
    for (int i = 0; i < n; i++) {
 
        // If current element is even
        if (a[i] % 2 == 0) {
            j++;
            swap(a[i], a[j]);
        }
    }
 
    j++;
 
    // Sort in decreasing order even part
    sort(a, a + j, greater<int>());
 
    // Sort in decreasing order odd part
    sort(a + j, a + n, greater<int>());
 
    int evenSum = 0, oddSum = 0;
 
    // Calculate sum of k
    // maximum even number
    for (int i = 0; i < k; i++) {
        evenSum += a[i];
    }
 
    // Calculate sum of k
    // maximum odd number
    for (int i = j; i < (j + k); i++) {
        oddSum += a[i];
    }
 
    // Print the absolute difference
    cout << abs(evenSum - oddSum);
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 8, 3, 4, 5 };
 
    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    int K = 2;
 
    // Function Call
    evenOddDiff(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the absolute
// difference between sum of first K
// maximum even and odd numbers
static void evenOddDiff(int a[], int n, int k)
{
     
    // Stores index from where odd
    // number starts
    int j = -1;
     
    Vector<Integer> even = new Vector<>();
    Vector<Integer> odd = new Vector<>();
     
    // Segregate even and odd number
    for(int i = 0; i < n; i++)
    {
         
        // If current element is even
        if (a[i] % 2 == 0)
        {
            even.add(a[i]);
        }
        else
            odd.add(a[i]);
    }
 
    j++;
 
    // Sort in decreasing order even part
    Collections.sort(even);
    Collections.reverse(even);
 
    // Sort in decreasing order odd part
    Collections.sort(odd);
    Collections.reverse(odd);
 
    int evenSum = 0, oddSum = 0;
 
    // Calculate sum of k
    // maximum even number
    for(int i = 0; i < k; i++)
    {
        evenSum += even.get(i);
    }
 
    // Calculate sum of k
    // maximum odd number
    for(int i = 0; i < k; i++)
    {
        oddSum += odd.get(i);
    }
 
    // Print the absolute difference
    System.out.print(Math.abs(evenSum - oddSum));
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int arr[] = { 1, 8, 3, 4, 5 };
 
    // Size of array
    int N = arr.length;
 
    int K = 2;
 
    // Function Call
    evenOddDiff(arr, N, K);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
 
# Function to find the absolute
# difference between sum of first K
# maximum even and odd numbers
def evenOddDiff(a, n, k) :
      
    # Stores index from where odd
    # number starts
    j = -1
      
    even = []
    odd = []
      
    # Segregate even and odd number
    for i in range(n) :
          
        # If current element is even
        if (a[i] % 2 == 0) :
         
            even.append(a[i])
        else :
            odd.append(a[i])
  
    j += 1
  
    # Sort in decreasing order even part
    even.sort()
    even.reverse()
  
    # Sort in decreasing order odd part
    odd.sort()
    odd.reverse()
  
    evenSum, oddSum = 0, 0
  
    # Calculate sum of k
    # maximum even number
    for i in range(k) :
 
        evenSum += even[i]
      
    # Calculate sum of k
    # maximum odd number
    for i in range(k) :
     
        oddSum += odd[i]
  
    # Print the absolute difference
    print(abs(evenSum - oddSum))
     
# Given array []arr
arr = [ 1, 8, 3, 4, 5 ]
  
# Size of array
N = len(arr)
 
K = 2
 
# Function Call
evenOddDiff(arr, N, K)
 
# This code is contributed by divyeshrabadiya07

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the absolute
// difference between sum of first K
// maximum even and odd numbers
static void evenOddDiff(int []a, int n,
                        int k)
{
     
    // Stores index from where odd
    // number starts
    int j = -1;
     
    List<int> even = new List<int>();
    List<int> odd = new List<int>();
     
    // Segregate even and odd number
    for(int i = 0; i < n; i++)
    {
         
        // If current element is even
        if (a[i] % 2 == 0)
        {
            even.Add(a[i]);
        }
        else
            odd.Add(a[i]);
    }
 
    j++;
 
    // Sort in decreasing order even part
    even.Sort();
    even.Reverse();
 
    // Sort in decreasing order odd part
    odd.Sort();
    odd.Reverse();
 
    int evenSum = 0, oddSum = 0;
 
    // Calculate sum of k
    // maximum even number
    for(int i = 0; i < k; i++)
    {
        evenSum += even[i];
    }
     
    // Calculate sum of k
    // maximum odd number
    for(int i = 0; i < k; i++)
    {
        oddSum += odd[i];
    }
 
    // Print the absolute difference
    Console.Write(Math.Abs(evenSum - oddSum));
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 1, 8, 3, 4, 5 };
     
    // Size of array
    int N = arr.Length;
 
    int K = 2;
 
    // Function Call
    evenOddDiff(arr, N, K);
}
}
 
// This code is contributed by Amit Katiyar

<script>
// javascript program for the above approach
 
    // Function to find the absolute
    // difference between sum of first K
    // maximum even and odd numbers
    function evenOddDiff(a , n , k) {
 
        // Stores index from where odd
        // number starts
        var j = -1;
 
        var even = [];
        var odd = [];
 
        // Segregate even and odd number
        for (i = 0; i < n; i++) {
 
            // If current element is even
            if (a[i] % 2 == 0) {
                even.push(a[i]);
            } else
                odd.push(a[i]);
        }
 
        j++;
 
        // Sort in decreasing order even part
        even.sort((a,b)=>a-b);
        even.reverse(even);
 
        // Sort in decreasing order odd part
        odd.sort((a,b)=>a-b);;
        odd.reverse();
 
        var evenSum = 0, oddSum = 0;
 
        // Calculate sum of k
        // maximum even number
        for (i = 0; i < k; i++) {
            evenSum += even[i];
        }
 
        // Calculate sum of k
        // maximum odd number
        for (i = 0; i < k; i++) {
            oddSum += odd[i];
        }
 
        // Print the absolute difference
        document.write(Math.abs(evenSum - oddSum));
    }
 
    // Driver Code
     
        // Given array arr
        var arr = [ 1, 8, 3, 4, 5 ];
 
        // Size of array
        var N = arr.length;
 
        var K = 2;
 
        // Function Call
        evenOddDiff(arr, N, K);
 
// This code is contributed by umadevi9616
</script>

4

Complejidad de tiempo: O(N*log N + K)
Espacio auxiliar: O(1)