Se requieren incrementos mínimos para hacer que los elementos de la array sean pares e impares alternativamente

Dada una array arr[] que consiste en N enteros positivos, la tarea es encontrar el número mínimo de incrementos requeridos para hacer que la array arr[] sea una secuencia alterna de números pares e impares.

Ejemplos:

Entrada: arr[] = {1, 4, 6, 8, 9, 5}
Salida: 2
Explicación:
Incrementar arr[2] modifica arr[] a {1, 4, 7, 8, 9, 5}.
Incrementar arr[5] en 1 modifica arr[] a {1, 4, 7, 8, 9, 6}.

Entrada: arr[] = {3, 5, 7, 9, 4, 2}
Salida: 3
Explicación:
Incrementar arr[0] en 1 modifica arr[] a {4, 5, 7, 9, 4, 2}.
Incrementar arr[2] en 1 modifica arr[] a {4, 5, 8, 9, 4, 2}.
Incrementar arr[5] en 1 modifica arr[] a {4, 5, 8, 9, 4, 3}.

Enfoque: Para resolver el problema dado, la idea es comprobar el número de incrementos necesarios para hacer que los elementos del arreglo sean pares e impares alternativamente, así como pares e impares alternativamente. Finalmente, imprima el mínimo de las dos cuentas de incrementos obtenidos. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos cnt como 0 , para almacenar el conteo de incrementos necesarios para convertir la array en una secuencia alterna de números pares e impares o viceversa.
• Recorra el arreglo arr[] usando la variable i y realice los siguientes pasos:
  • Si i es par y arr[i] es impar, entonces incremente cnt en 1.
  • Si i es impar y arr[i] es par, entonces incremente cnt en 1.
• Después de completar los pasos anteriores, el mínimo de cnt y (N – cnt) es el resultado requerido.

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

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to find the minimum number of
// increments required to make the array
// even-odd alternately or vice-versa
int minIncr(int *arr,int n)
{
   
    // Store the minimum number of
    // increments required
    int forEven = 0;
   
    // Traverse the array arr[]
    for(int i = 0; i < n; i++)
    {
       
        // Increment forEven if even
        // element is present at an
        // odd index
        if(i % 2){
            if((arr[i] % 2) == 0)
                forEven += 1;
        }
       
        // Increment forEven if odd
        // element is present at an
        // even index
        else{
            if(arr[i] % 2)
                forEven += 1;
        }
    }
   
    // Return the minimum number of increments
    return min(forEven, n - forEven);
}
 
int main()
{
   
    // Driver Code
    int arr[] = {1, 4, 6, 8, 9, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<minIncr(arr,n);
    return 0;
}
 
// This code is contributed by rohitsingh07052.

// Java program for the above approach
class GFG{
     
// Function to find the minimum number of
// increments required to make the array
// even-odd alternately or vice-versa
static int minIncr(int []arr, int n)
{
     
    // Store the minimum number of
    // increments required
    int forEven = 0;
   
    // Traverse the array arr[]
    for(int i = 0; i < n; i++)
    {
         
        // Increment forEven if even
        // element is present at an
        // odd index
        if (i % 2 == 1)
        {
            if ((arr[i] % 2) == 0)
                forEven += 1;
        }
       
        // Increment forEven if odd
        // element is present at an
        // even index
        else
        {
            if (arr[i] % 2 == 1)
                forEven += 1;
        }
    }
   
    // Return the minimum number of increments
    return Math.min(forEven, n - forEven);
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 1, 4, 6, 8, 9, 5 };
    int n = arr.length;
     
    System.out.println(minIncr(arr,n));
}
}
 
// This code is contributed by AnkThon

# Python3 program for the above approach
 
# Function to find the minimum number of
# increments required to make the array
# even-odd alternately or vice-versa
def minIncr(arr):
 
    # Store the minimum number of
    # increments required
    forEven = 0
 
    # Traverse the array arr[]
    for i in range(len(arr)):
 
        # Increment forEven if even
        # element is present at an
        # odd index
        if i % 2:
            if not arr[i] % 2:
                forEven += 1
 
        # Increment forEven if odd
        # element is present at an
        # even index
        else:
            if arr[i] % 2:
                forEven += 1
 
    # Return the minimum number of increments
    return min(forEven, len(arr)-forEven)
 
 
# Driver Code
arr = [1, 4, 6, 8, 9, 5]
print(minIncr(arr))

// C# program for the above approach
using System;
public class GFG
{
 
  // Function to find the minimum number of
  // increments required to make the array
  // even-odd alternately or vice-versa
  static int minIncr(int []arr, int n)
  {
 
    // Store the minimum number of
    // increments required
    int forEven = 0;
 
    // Traverse the array []arr
    for(int i = 0; i < n; i++)
    {
 
      // Increment forEven if even
      // element is present at an
      // odd index
      if (i % 2 == 1)
      {
        if ((arr[i] % 2) == 0)
          forEven += 1;
      }
 
      // Increment forEven if odd
      // element is present at an
      // even index
      else
      {
        if (arr[i] % 2 == 1)
          forEven += 1;
      }
    }
 
    // Return the minimum number of increments
    return Math.Min(forEven, n - forEven);
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []arr = { 1, 4, 6, 8, 9, 5 };
    int n = arr.Length;
 
    Console.WriteLine(minIncr(arr,n));
  }
}
 
// This code is contributed by shikhasingrajput

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum number of
// increments required to make the array
// even-odd alternately or vice-versa
function minIncr(arr, n)
{
   
    // Store the minimum number of
    // increments required
    let forEven = 0;
   
    // Traverse the array arr[]
    for(let i = 0; i < n; i++)
    {
       
        // Increment forEven if even
        // element is present at an
        // odd index
        if(i % 2){
            if((arr[i] % 2) == 0)
                forEven += 1;
        }
       
        // Increment forEven if odd
        // element is present at an
        // even index
        else{
            if(arr[i] % 2)
                forEven += 1;
        }
    }
   
    // Return the minimum number of increments
    return Math.min(forEven, n - forEven);
}
 
// Driver Code
let arr = [1, 4, 6, 8, 9, 5];
let n = arr.length;
document.write(minIncr(arr,n));
 
</script>

2

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