Minimice los intercambios para reorganizar la array de manera que la paridad del índice y el elemento correspondiente sea la misma

Dada una array A[], la tarea de encontrar las operaciones de intercambio mínimas necesarias para modificar la array dada A[] de modo que para cada índice de la array, paridad(i) = paridad(A[i]) donde paridad(x) = x % 2 . Si es imposible obtener tal arreglo, imprima -1.

Ejemplos:

Entrada: A[] = { 2, 4, 3, 1, 5, 6 } 
Salida: 2 
Explicación: 
Intercambiar (4, 3) y (5, 6) modifica la array a [2, 3, 4, 1, 6 , 5] tal que la paridad de i y A[i] es la misma para todos los índices.

Entrada: A[] = {1, 2, 5, 7} 
Salida: -1 
Explicación: 
La array dada no se puede reorganizar según la condición requerida.

Enfoque: 
para resolver el problema mencionado anteriormente, un enfoque óptimo es elegir un índice en el que la paridad (i) y la paridad (A [i]) no sean lo mismo.

• Inicialice dos variables needodd y needeven a 0 que almacenarán la paridad de cada elemento. Verifique la paridad del índice si es impar, luego aumente el valor de needodd en 1; de lo contrario, aumente needeven .
• Si needodd y needeven no son lo mismo, entonces el arreglo requerido no es posible.
• En caso contrario, el resultado final se obtiene mediante la variable needodd , ya que es el número de operaciones que se requieren. Esto se debe a que, en cualquier momento, elegimos un elemento impar cuya paridad no es la misma que la paridad de su índice y, de manera similar, elegimos un elemento par y los intercambiamos.

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

// C++ implementation to minimize
// swaps required to rearrange
// array such that parity of index and
// corresponding element is same
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// parity of number
int parity(int x)
{
    return x % 2;
     
}
 
// Function to return minimum
// number of operations required
int solve(int a[], int size)
{
     
    // Initialize needodd and
    // needeven value by 0
    int needeven = 0;
    int needodd = 0;
     
    for(int i = 0; i < size; i++)
    {
        if(parity(i) != parity(a[i]))
        {
             
            // Check if parity(i) is odd
            if(parity(i) % 2)
            {
                 
                // increase needodd
                // as we need odd no
                // at that position.
                needodd++;
            }
            else
            {
 
                // increase needeven
                // as we need even
                // number at that position
                needeven++;
            }
        }
    }
     
    // If needeven and needodd are unequal
    if(needeven != needodd)
        return -1;
    else
        return needodd;
}
 
// Driver Code
int main()
{
    int a[] = { 2, 4, 3, 1, 5, 6};
    int n = sizeof(a) / sizeof(a[0]);
 
    // Function call
    cout << solve(a, n) << endl;
 
    return 0;
}
 
// This code is contributed by venky07

// Java implementation to minimize 
// swaps required to rearrange 
// array such that parity of index and 
// corresponding element is same
import java.util.*;
 
class GFG{
     
// Function to return the
// parity of number
static int parity(int x)
{
    return x % 2;
}
 
// Function to return minimum
// number of operations required
static int solve(int a[], int size)
{
     
    // Initialize needodd and
    // needeven value by 0
    int needeven = 0;
    int needodd = 0;
     
    for(int i = 0; i < size; i++)
    {
        if(parity(i) != parity(a[i]))
        {
             
            // Check if parity(i) is odd
            if(parity(i) % 2 == 1)
            {
                 
                // Increase needodd
                // as we need odd no
                // at that position.
                needodd++;
            }
            else
            {
                 
                // Increase needeven
                // as we need even
                // number at that position
                needeven++;
            }
        }
    }
     
    // If needeven and needodd are unequal
    if(needeven != needodd)
        return -1;
    else
        return needodd;
}
 
// Driver Code
public static void main (String[] args)
{
    int a[] = { 2, 4, 3, 1, 5, 6};
    int n = a.length;
     
    // Function call
    System.out.println(solve(a, n));
}
}
 
// This code is contributed by offbeat

# Python3 implementation to minimize
# swaps required to rearrange
# array such that parity of index and
# corresponding element is same
 
# Function to return the
# parity of number
def parity(x):
    return x % 2
 
# Function to return minimum
# number of operations required
 
def solve(a, size):
     
    # Initialize needodd and
    # needeven value by 0
    needeven = 0
    needodd = 0
    for i in range(size):
                 
        if parity(i)!= parity(a[i]):
             
            # Check if parity(i) is odd
            if parity(i) % 2:
                 
                # increase needodd
                # as we need odd no
                # at that position.
                needodd+= 1
            else:
                # increase needeven
                # as we need even
                # number at that position
                needeven+= 1
     
    # If needeven and needodd are unequal
    if needodd != needeven:
        return -1
         
    return needodd
     
# Driver code    
if __name__ =="__main__":
     
    a = [2, 4, 3, 1, 5, 6]
    n = len(a)
    print(solve(a, n))

// C# implementation to minimize 
// swaps required to rearrange 
// array such that parity of index and 
// corresponding element is same
using System;
class GFG{
     
// Function to return the
// parity of number
static int parity(int x)
{
  return x % 2;
}
 
// Function to return minimum
// number of operations required
static int solve(int[] a, int size)
{    
  // Initialize needodd and
  // needeven value by 0
  int needeven = 0;
  int needodd = 0;
 
  for(int i = 0; i < size; i++)
  {
    if(parity(i) != parity(a[i]))
    {
      // Check if parity(i) is odd
      if(parity(i) % 2 == 1)
      {
        // Increase needodd
        // as we need odd no
        // at that position.
        needodd++;
      }
      else
      {
        // Increase needeven
        // as we need even
        // number at that position
        needeven++;
      }
    }
  }
 
  // If needeven and needodd are unequal
  if(needeven != needodd)
    return -1;
  else
    return needodd;
}
 
// Driver Code
public static void Main ()
{
  int[] a = {2, 4, 3, 1, 5, 6};
  int n = a.Length;
 
  // Function call
  Console.Write(solve(a, n));
}
}
 
// This code is contributed by Chitranayal

<script>
 
// Javascript implementation to minimize
// swaps required to rearrange array such
// that parity of index and corresponding
// element is same
 
// Function to return the
// parity of number
function parity(x)
{
    return x % 2;
}
 
// Function to return minimum
// number of operations required
function solve(a, size)
{
     
    // Initialize needodd and
    // needeven value by 0
    let needeven = 0;
    let needodd = 0;
     
    for(let i = 0; i < size; i++)
    {
        if (parity(i) != parity(a[i]))
        {
             
            // Check if parity(i) is odd
            if (parity(i) % 2 == 1)
            {
                 
                // Increase needodd
                // as we need odd no
                // at that position.
                needodd++;
            }
            else
            {
                 
                // Increase needeven
                // as we need even
                // number at that position
                needeven++;
            }
        }
    }
     
    // If needeven and needodd are unequal
    if (needeven != needodd)
        return -1;
    else
        return needodd;
}
 
// Driver code
let a = [ 2, 4, 3, 1, 5, 6 ];
let n = a.length;
 
// Function call
document.write(solve(a, n));
 
// This code is contributed by rameshtravel07
 
</script>

2

Complejidad de tiempo: O(n), donde n es el tamaño de la array dada
Espacio auxiliar: O(1)