Número mínimo de monedas necesarias para eliminar todos los elementos de la array según las reglas dadas

Dada una array arr de longitud N con valores 1 y 2 que indican elementos de tipo 1 y tipo 2 y dos jugadores, jugador1 y jugador2. La tarea es encontrar la cantidad mínima de monedas necesarias para eliminar todos los elementos en el orden dado en la array. Se deben seguir las siguientes reglas:

• Player1 y Player2 se turnan para eliminar elementos con Player1 comenzando primero
• Ambos pueden eliminar como máximo 2 elementos adyacentes y deben eliminar al menos un elemento en su turno
• El elemento tipo 2 puede ser eliminado por ambos sin una moneda
• El jugador 2 puede eliminar el elemento de tipo 1 sin una moneda, pero el jugador 1 necesitará una moneda para eliminar el elemento.

Ejemplo:

Entrada: N = 8 arr = [1, 2, 1, 1, 2, 1, 1, 1]
Salida: 2
Explicación: El total de monedas que necesita el jugador 1 es 2. A continuación se muestran los elementos eliminados en el turno de cada jugador:

• El jugador 1 eliminará el primer elemento de tipo 1 con una moneda y el segundo elemento de tipo 2 sin moneda.
• Player2 eliminará los siguientes dos elementos
• Player1 comenzará su operación y eliminará solo el siguiente elemento de tipo 2 sin una moneda
• Player2 comenzará su operación y eliminará los siguientes dos elementos en el índice 5 y 6 en la array
• Player1 eliminará el último elemento de tipo 1 usando una moneda

Entrada:  N = 4 arr = [1, 1, 2, 2]
Salida: 2
Explicación: El total de monedas que necesita el jugador 1 es 1. A continuación se muestran los elementos eliminados en el turno de cada jugador

• Player1 eliminará el primer elemento de tipo 1 usando una moneda
• Player2 eliminará el segundo y el tercer elemento
• Player1 eliminará el cuarto elemento de tipo 2 sin una moneda

Enfoque:  el problema dado se puede resolver con un enfoque codicioso utilizando dos punteros. Se pueden seguir los siguientes pasos para resolver el problema:

• El primer elemento se considera por separado. Si es del tipo 1, se agregará 1 al total de monedas necesarias para eliminar los elementos.
• Iterar la array desde el segundo índice considerando el turno de su Player1
• Si en el turno del Jugador 1 y el primer elemento es del tipo 2 y el siguiente elemento del tipo 1, el Jugador 1 eliminará solo el elemento del tipo 2 y luego el Jugador 2 puede comenzar la operación.
• Si en el turno del Jugador 1 y dos elementos consecutivos de tipo 2, en esa operación el Jugador 1 eliminará ambos elementos.
• Si en el turno del Jugador 1 hay 3 elementos consecutivos de tipo 1, el Jugador 1 solo eliminará el primer elemento con una moneda y el Jugador 2 podrá eliminar los siguientes dos elementos.
• Teniendo en cuenta los tres casos anteriores, se puede hacer una observación de que cada fragmento de elementos de tipo 1 comienza con la operación de Player2
• Por lo tanto, por cada tres elementos consecutivos de tipo 1, se puede ver que el Jugador 1 necesita una moneda para eliminar un elemento y el Jugador 2 eliminará dos elementos.

// C++ implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum
// number of coins needed
int minimumcoins(int arr[], int N)
{
 
    int coins = 0;
    int j = 0;
 
    // Consider the first element
    // separately, add 1 to the total
    // if it's of type 1
    if (arr[0] == 1)
        coins++;
 
    // Iterate from the second element
    for (int i = 1; i < N; i++) {
        // If the current element is
        // of type 2 then any Player
        // can remove the element
        if (arr[i] == 2)
            continue;
 
        // Second pointer to reach end of
        // type 1 elements
        j = i;
 
        // Increment j until arr[j]
        // is equal to 1 and j is not
        // out of bounds
        while (j < N && arr[j] == 1) {
            j++;
        }
 
        // Number of type 1 elements
        // in a continuous chunk
        int x = (j - i);
        coins += x / 3;
 
        // From next iteration i
        // pointer will start from
        // index of j
        i = j - 1;
    }
 
    // Return the minimum count of coins
    return coins;
}
 
int main()
 
{
 
    int N = 8;
 
    int arr[] = { 1, 2, 1, 1, 2, 1, 1, 1 };
 
    cout << minimumcoins(arr, N);
 
    return 0;
}

// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
 
    // Function to calculate minimum
    // number of coins needed
    static int minimumcoins(int arr[], int N)
    {
 
        int coins = 0;
        int j = 0;
 
        // Consider the first element
        // separately, add 1 to the total
        // if it's of type 1
        if (arr[0] == 1)
            coins++;
 
        // Iterate from the second element
        for (int i = 1; i < N; i++) {
            // If the current element is
            // of type 2 then any Player
            // can remove the element
            if (arr[i] == 2)
                continue;
 
            // Second pointer to reach end of
            // type 1 elements
            j = i;
 
            // Increment j until arr[j]
            // is equal to 1 and j is not
            // out of bounds
            while (j < N && arr[j] == 1) {
                j++;
            }
 
            // Number of type 1 elements
            // in a continuous chunk
            int x = (j - i);
            coins += x / 3;
 
            // From next iteration i
            // pointer will start from
            // index of j
            i = j - 1;
        }
 
        // Return the minimum count of coins
        return coins;
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int N = 8;
 
        int arr[] = { 1, 2, 1, 1, 2, 1, 1, 1 };
        // Function Call
        System.out.println(minimumcoins(arr, N));
    }
}
 
// This code is contributed by dwivediyash

# Python program for the above approach
 
# Function to calculate minimum
# number of coins needed
def minimumcoins(arr, N) :
 
    coins = 0
    j = 0
 
    # Consider the first element
    # separately, add 1 to the total
    # if it's of type 1
    if (arr[0] == 1) :
        coins += 1
 
    # Iterate from the second element
    for i in range(1, N) :
        # If the current element is
        # of type 2 then any Player
        # can remove the element
        if (arr[i] == 2) :
            continue
 
        # Second pointer to reach end of
        # type 1 elements
        j = i
 
        # Increment j until arr[j]
        # is equal to 1 and j is not
        # out of bounds
        while (j < N and arr[j] == 1) :
            j += 1
         
 
        # Number of type 1 elements
        # in a continuous chunk
        x = (j - i)
        coins += x // 3
 
        # From next iteration i
        # pointer will start from
        # index of j
        i = j - 1
     
    # Return the minimum count of coins
    return coins
 
# Driver Code
N = 8
arr = [ 1, 2, 1, 1, 2, 1, 1, 1 ]
 
print(minimumcoins(arr, N))
 
# This code is contributed by sanjoy_62.

// C# implementation for the above approach
using System;
 
public class GFG {
 
    // Function to calculate minimum
    // number of coins needed
    static int minimumcoins(int []arr, int N)
    {
 
        int coins = 0;
        int j = 0;
 
        // Consider the first element
        // separately, add 1 to the total
        // if it's of type 1
        if (arr[0] == 1)
            coins++;
 
        // Iterate from the second element
        for (int i = 1; i < N; i++) {
            // If the current element is
            // of type 2 then any Player
            // can remove the element
            if (arr[i] == 2)
                continue;
 
            // Second pointer to reach end of
            // type 1 elements
            j = i;
 
            // Increment j until arr[j]
            // is equal to 1 and j is not
            // out of bounds
            while (j < N && arr[j] == 1) {
                j++;
            }
 
            // Number of type 1 elements
            // in a continuous chunk
            int x = (j - i);
            coins += x / 3;
 
            // From next iteration i
            // pointer will start from
            // index of j
            i = j - 1;
        }
 
        // Return the minimum count of coins
        return coins;
    }
   
    // Driver Code
    public static void Main(String[] args)
    {
        int N = 8;
 
        int []arr = { 1, 2, 1, 1, 2, 1, 1, 1 };
         
        // Function Call
        Console.WriteLine(minimumcoins(arr, N));
    }
}
 
// This code is contributed by AnkThon

<script>
 
// JavaScript implementation for the above approach
 
// Function to calculate minimum
// number of coins needed
function minimumcoins(arr, N)
{
    let coins = 0;
    let j = 0;
     
    // Consider the first element
    // separately, add 1 to the total
    // if it's of type 1
    if (arr[0] == 1)
        coins++;
 
    // Iterate from the second element
    for(let i = 1; i < N; i++)
    {
         
        // If the current element is
        // of type 2 then any Player
        // can remove the element
        if (arr[i] == 2)
            continue;
 
        // Second pointer to reach end of
        // type 1 elements
        j = i;
 
        // Increment j until arr[j]
        // is equal to 1 and j is not
        // out of bounds
        while (j < N && arr[j] == 1)
        {
            j++;
        }
 
        // Number of type 1 elements
        // in a continuous chunk
        let x = (j - i);
        coins += Math.floor(x / 3);
 
        // From next iteration i
        // pointer will start from
        // index of j
        i = j - 1;
    }
 
    // Return the minimum count of coins
    return coins;
}
 
// Driver code
let N = 8;
let arr = [ 1, 2, 1, 1, 2, 1, 1, 1 ];
 
document.write(minimumcoins(arr, N));
 
// This code is contributed by Potta Lokesh
 
</script>

2

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