Minimice las eliminaciones de modo que ningún elemento Array de índice par sea igual al elemento siguiente

Dada una array arr[] , la tarea es encontrar el número mínimo de operaciones de eliminación necesarias de modo que:

• La array recién creada debe tener una longitud uniforme.
• arr[i] ≠ arr[i+1] para cada i donde i%2==0 .

Ejemplos:

Entrada: arr[] = {1, 1, 2, 3, 5}
Salida: 1
Explicación: elimine el primer o segundo elemento de la array para satisfacer las condiciones.

Entrada: arr[]= {1, 1, 2, 2, 3, 3}
Salida: 2
Explicación: elimine el primer elemento ya que el siguiente elemento es un duplicado y el índice actual es par. 
Necesita eliminar otro elemento de la array recién creada porque 
el tamaño de la array recién creada es impar. arr = {1, 2, 2, 3, 3}
Elimina el último elemento para que su longitud sea uniforme. Así que el número total de operaciones es 2.

Enfoque: La idea general para resolver este problema es:

Maximice la cantidad de elementos en la array recién creada y siga verificando si algún elemento de índice par tiene el mismo valor que el que está justo al lado. 

La idea anterior se puede implementar usando una pila para generar la nueva array. Siga los pasos mencionados a continuación para implementar la observación anterior:

• Cree una pila de pares para almacenar los elementos y el índice del elemento en la nueva array.
• Iterar sobre la array arr[] de i = 0 a N-1 :
  • Si el índice del elemento superior de la pila es impar, empuje el elemento actual junto con su índice en la nueva array de la pila.
  • De lo contrario, compruebe si el valor de arr[i] y el elemento superior son iguales.
    • Si son iguales, continúe con el siguiente elemento de arr[] .
    • De lo contrario, agregue el elemento actual en la nueva array. puntero de índice a la pila.
• Por último, si el tamaño de la pila es impar, elimine un elemento más de la pila. 
• Devuelva el valor de N – tamaño de pila como respuesta, porque este es el número mínimo de eliminaciones requeridas.

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

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum deletions
int minOperations(vector<int>& arr)
{
    int n = arr.size();
   
    // Stack that will maintain the newly
    // created array
    stack<pair<int, int> > st;
    int k = 1;
   
    // Pushed the first element to the stack.
    st.push({ arr[0], 0 });
    for (int i = 1; i < n; i++) {
         
        // If the top most element in the
        // stack is at even index and the
        // element is same as the current
        // array element then continue.
        if (st.top().second % 2 == 0
            && st.top().first == arr[i]) {
            continue;
        }
         
        // If the top most element in the stack
        // is at odd index or the two elements
        // are not same then push the current
        // element to the stack.
        else {
            st.push({ arr[i], k });
            k++;
        }
    }
 
    // Find the stack size
    int s = st.size();
   
    // If stack size is odd then
    // delete further one element
    // from stack, hence return
    // array size - stack size +1.
    if (s & 1 == 1) {
        return n - s + 1;
    }
   
    // Return (array size - stack size).
    return n - s;
}
 
// Driver code
int main()
{
    vector<int> arr = { 1, 1, 2, 3, 5 };
   
    // Function call
    cout << minOperations(arr);
    return 0;
}

// Java program for above approach
import java.util.Stack;
 
class GFG
{
 
  // Function to find the minimum deletions
  static int minOperations(int[] arr)
  {
    int n = arr.length;
 
    // Stack that will maintain the newly
    // created array
    Stack<int[]> st = new Stack<>();
    int k = 1;
 
    // Pushed the first element to the stack.
    int[] stFirstElem = { arr[0], 0 };
    st.push(stFirstElem);
    for (int i = 1; i < n; i++) {
 
      // If the top most element in the
      // stack is at even index and the
      // element is same as the current
      // array element then continue.
      if (st.peek()[1] % 2 == 0
          && st.peek()[1] == arr[i]) {
        continue;
      }
 
      // If the top most element in the stack
      // is at odd index or the two elements
      // are not same then push the current
      // element to the stack.
      else {
        int[] stElem = { arr[i], k };
        st.push(stElem);
        k++;
      }
    }
 
    // Find the stack size
    int s = st.size();
 
    // If stack size is odd then
    // delete further one element
    // from stack, hence return
    // array size - stack size +1.
    if ((s & 1) == 1) {
      return n - s + 1;
    }
 
    // Return (array size - stack size).
    return n - s;
  }
 
  // driver code
  public static void main(String[] args)
  {
    int[] arr = { 1, 1, 2, 3, 5 };
 
    // Function call
    System.out.print(minOperations(arr));
  }
}
 
// This code is contributed by phasing17

# Python3 program for above approach
 
# Function to find the minimum deletions
def minOperations(arr):
    n = len(arr)
 
    # stack that will maintain
    # the newly created array
    st = []
    k = 1
 
    # Pushed the first element to the stack
    st.append([arr[0], 0])
    for i in range(1, n):
       
        # If the top most element in the
        # stack is at even index and the
        # element is same as the current
        # array element then continue
        if st[len(st) - 1][1] % 2 == 0 and st[len(st) - 1][0] == arr[i]:
            continue
             
        # If the top most element in the stack
        # is at odd index or the two elements
        # are not same then push the current
        # element to the stack.
        else:
            st.append([arr[i], k])
            k += 1
             
    # Find the stack size
    s = len(st)
     
    # If stack size is odd then
    # delete further one element
    # from stack, hence return
    # array size - stack size +1.
    if s & 1 == 1:
        return n - s + 1
    # Return (array size - stack size).
    return n - s
 
# Driver code
arr = [1, 1, 2, 3, 5]
 
# Function call
print(minOperations(arr))
 
# This code is contributed by phasing17

// C# program for above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to find the minimum deletions
  static int minOperations(int[] arr)
  {
    int n = arr.Length;
 
    // Stack that will maintain the newly
    // created array
    Stack<int[]> st = new Stack<int[]>();
    int k = 1;
 
    // Pushed the first element to the stack.
    int[] stFirstElem = { arr[0], 0 };
    st.Push(stFirstElem);
    for (int i = 1; i < n; i++) {
 
      // If the top most element in the
      // stack is at even index and the
      // element is same as the current
      // array element then continue.
      if (st.Peek()[1] % 2 == 0
          && st.Peek()[1] == arr[i]) {
        continue;
      }
 
      // If the top most element in the stack
      // is at odd index or the two elements
      // are not same then push the current
      // element to the stack.
      else {
        int[] stElem = { arr[i], k };
        st.Push(stElem);
        k++;
      }
    }
 
    // Find the stack size
    int s = st.Count;
 
    // If stack size is odd then
    // delete further one element
    // from stack, hence return
    // array size - stack size +1.
    if ((s & 1) == 1) {
      return n - s + 1;
    }
 
    // Return (array size - stack size).
    return n - s;
  }
 
  // driver code
  public static void Main()
  {
    int[] arr = { 1, 1, 2, 3, 5 };
 
    // Function call
    Console.Write(minOperations(arr));
  }
}
 
// This code is contributed by jana_sayantan.

<script>
    // JavaScript program for above approach
 
    // Function to find the minimum deletions
    const minOperations = (arr) => {
        let n = arr.length;
 
        // Stack that will maintain the newly
        // created array
        let st = [];
        let k = 1;
 
        // Pushed the first element to the stack.
        st.push([arr[0], 0]);
        for (let i = 1; i < n; i++) {
 
            // If the top most element in the
            // stack is at even index and the
            // element is same as the current
            // array element then continue.
            if (st[st.length - 1][1] % 2 == 0
                && st[st.length - 1][0] == arr[i]) {
                continue;
            }
 
            // If the top most element in the stack
            // is at odd index or the two elements
            // are not same then push the current
            // element to the stack.
            else {
                st.push([arr[i], k]);
                k++;
            }
        }
 
        // Find the stack size
        let s = st.length;
 
        // If stack size is odd then
        // delete further one element
        // from stack, hence return
        // array size - stack size +1.
        if (s & 1 == 1) {
            return n - s + 1;
        }
 
        // Return (array size - stack size).
        return n - s;
    }
 
    // Driver code
    let arr = [1, 1, 2, 3, 5];
 
    // Function call
    document.write(minOperations(arr));
 
// This code is contributed by rakeshsahni
 
</script>

1

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