Imprima la array lexicográficamente más pequeña intercambiando elementos cuya suma es impar

Dada una array de N enteros. La tarea es encontrar la array lexicográficamente más pequeña posible aplicando la operación dada cualquier número de veces. La operación es elegir dos elementos a _i y a _j (1<=i, j<=N) tales que a _i + a _j sea impar, y luego intercambiar a _i y a _j . 
Ejemplos: 
 

Entrada: a[] = {1, 5, 4, 3, 2} 
Salida: 1 2 3 4 5 
Explicación: Primero intercambie (5, 2) y luego (4, 3). Esta es la 
array lexicográficamente más pequeña posible que se puede obtener mediante el 
intercambio de elementos de la array que satisface la condición dada
Entrada: a[] = {4, 2} 
Salida: 4 2 
Explicación: No es posible intercambiar ningún elemento.

Enfoque : observe que el intercambio de 2 elementos es posible si tienen una paridad diferente. Si todos los elementos de la array tienen la misma paridad (impar + impar y par + par no es impar) , no es posible realizar intercambios. Por lo tanto, la respuesta será solo la array de entrada. De lo contrario, puede intercambiar cualquier par de elementos. Suponga que desea intercambiar 2 elementos, a y b, y tienen la misma paridad. Debe haber un tercer elemento c que tenga una paridad diferente. Sin pérdida de generalidad, suponga que la array es [a, b, c] . Hagamos los siguientes intercambios:
 

• Intercambiar a y c:
• Intercambiar b y c: [b, c, a]
• Intercambiar a y c: [b, a, c]

En otras palabras, use c como un elemento intermedio para intercambiar a y b, y luego siempre volverá a su posición original. Dado que el intercambio es posible entre cualquier par de elementos, siempre podemos ordenar la array, que será la array lexicográficamente más pequeña. 
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find possible
// lexicographically smaller array
// by swapping only elements whose sum is odd
#include <bits/stdc++.h>
using namespace std;
 
// Function to find possible lexicographically smaller array
void lexicographically_smaller(int arr[], int n)
{
    // To store number of even and odd integers
    int odd = 0, even = 0;
 
    // Find number of even and odd integers
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2)
            odd++;
        else
            even++;
    }
 
    // If it possible to make
    // lexicographically smaller
    if (odd && even)
        sort(arr, arr + n);
 
    // Print the array
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int arr[] = { 1, 5, 4, 3, 2 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    lexicographically_smaller(arr, n);
 
    return 0;
}

// Java program to find possible
// lexicographically smaller array
// by swapping only elements whose sum is odd
import java.util.*;
 
class GFG
{
 
// Function to find possible lexicographically smaller array
static void lexicographically_smaller(int arr[], int n)
{
    // To store number of even and odd integers
    int odd = 0, even = 0;
 
    // Find number of even and odd integers
    for (int i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 1)
            odd++;
        else
            even++;
    }
 
    // If it possible to make
    // lexicographically smaller
    if (odd > 0 && even > 0)
        Arrays.sort(arr);
 
    // Print the array
    for (int i = 0; i < n; i++)
        System.out.print(arr[i] + " ");
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 5, 4, 3, 2 };
 
    int n = arr.length;
 
    // Function call
    lexicographically_smaller(arr, n);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to find possible
# lexicographically smaller array
# by swapping only elements whose sum is odd
 
# Function to find possible
# lexicographically smaller array
def lexicographically_smaller(arr, n):
     
    # To store number of even and odd integers
    odd, even = 0, 0;
 
    # Find number of even and odd integers
    for i in range(n):
        if (arr[i] % 2 == 1):
            odd += 1;
        else:
            even += 1;
 
    # If it possible to make
    # lexicographically smaller
    if (odd > 0 and even > 0):
        arr.sort();
 
    # Print the array
    for i in range(n):
        print(arr[i], end = " ");
 
# Driver code
if __name__ == '__main__':
 
    arr = [ 1, 5, 4, 3, 2 ];
 
    n = len(arr);
 
    # Function call
    lexicographically_smaller(arr, n);
 
# This code contributed by Rajput-Ji

// C# program to find possible
// lexicographically smaller array by
// swapping only elements whose sum is odd
using System;
     
class GFG
{
 
// Function to find possible
// lexicographically smaller array
static void lexicographically_smaller(int []arr, int n)
{
    // To store number of even and odd integers
    int odd = 0, even = 0;
 
    // Find number of even and odd integers
    for (int i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 1)
            odd++;
        else
            even++;
    }
 
    // If it possible to make
    // lexicographically smaller
    if (odd > 0 && even > 0)
        Array.Sort(arr);
 
    // Print the array
    for (int i = 0; i < n; i++)
        Console.Write(arr[i] + " ");
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 1, 5, 4, 3, 2 };
 
    int n = arr.Length;
 
    // Function call
    lexicographically_smaller(arr, n);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// javascript program to find possible
// lexicographically smaller array
// by swapping only elements whose sum is odd
 
// Function to find possible lexicographically smaller array
function lexicographically_smaller(arr , n)
{
    // To store number of even and odd integers
    var odd = 0, even = 0;
 
    // Find number of even and odd integers
    for (var i = 0; i < n; i++)
    {
        if (arr[i] % 2 == 1)
            odd++;
        else
            even++;
    }
 
    // If it possible to make
    // lexicographically smaller
    if (odd > 0 && even > 0)
        arr.sort((a,b)=>a-b);
 
    // Print the array
    for (i = 0; i < n; i++)
        document.write(arr[i] + " ");
}
 
// Driver code
var arr = [ 1, 5, 4, 3, 2 ];
 
var n = arr.length;
 
// Function call
lexicographically_smaller(arr, n);
 
 
// This code is contributed by 29AjayKumar
</script>

1 2 3 4 5

Complejidad de tiempo : O (N log N)