Minimice las eliminaciones consecutivas de elementos del mismo tipo para vaciar la array dada

Dada una array A[ ] que consta de N enteros positivos , de modo que cada elemento de la array A _i denota el recuento de elementos del i ^-ésimo tipo, la tarea es minimizar el número de eliminaciones de elementos consecutivos del mismo tipo para vaciar la array dada. .

Ejemplos: 

Entrada: A[ ] = {3, 3, 2} 
Salida: 0 
Explicación: La array consta de 3, 3, 2 elementos de 1 ^er , 2 ^nd y 3 ^rd tipo respectivamente. Al eliminar los elementos de la array en el orden {2, 1, 2, 3, 1, 3, 1}, se obtiene una secuencia en la que no se eliminan dos elementos consecutivos que sean del mismo tipo. Por lo tanto, la cuenta es 0.

Entrada: A [ ] = {1, 4, 1} 
Salida: 1 
Explicación: La array consta de 1, 4, 1 elementos de 1 ^er , 2 ^nd y 3 ^rd tipo respectivamente. Al eliminar los elementos de la array en el orden {2, 3, 2, 2, 1, 2}, las eliminaciones consecutivas de elementos del mismo tipo se reducen a 1. Por lo tanto, el recuento es 1. 

Enfoque: el problema se puede resolver con el enfoque codicioso . Siga los pasos a continuación para resolver el problema: 

• Ordenar la array dada .
• Calcular la suma de los elementos del arreglo.
• Encuentre el elemento más grande presente en la array , que es A _N-1. .
• Si la diferencia entre la suma y el elemento máximo es mayor que el elemento máximo, imprima 0 como respuesta requerida.
• De lo contrario, imprima 2* max – sum -1 como la respuesta requerida.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to count minimum consecutive
// removals of elements of the same type
void minRemovals(int A[], int N)
{
  
    // Sort the array
    sort(A, A + N);
  
    // Stores the maximum element
    // present in the array
    int mx = A[N - 1];
  
    // Stores sum of the array
    int sum = 1;
  
    // Calculate sum of the array
    for (int i = 0; i < N; i++) {
        sum += A[i];
    }
  
    if (sum - mx >= mx) {
        cout << 0 << "\n";
    }
    else {
        cout << 2 * mx - sum << "\n";
    }
}
  
// Driver Code
int main()
{
    int A[] = { 3, 3, 2 };
    int N = sizeof(A) / sizeof(A[0]);
  
    // Function call
    minRemovals(A, N);
    return 0;
}

// Java implementation of the above approach
import java.util.Arrays;
  
class GFG 
{
      
    // Function to count minimum consecutive
    // removals of elements of the same type
    static void minRemovals(int []A, int N)
    {
      
        // Sort the array
        Arrays.sort(A);
      
        // Stores the maximum element
        // present in the array
        int mx = A[N - 1];
      
        // Stores sum of the array
        int sum = 1;
      
        // Calculate sum of the array
        for (int i = 0; i < N; i++)
        {
            sum += A[i];
        }
      
        if (sum - mx >= mx) {
            System.out.println(0);
        }
        else {
            System.out.println(2 * mx - sum);
        }
    }
      
    // Driver Code
    public static void main(String[] args) {
          
        int []A = { 3, 3, 2 };
        int N = A.length;
      
        // Function call
        minRemovals(A, N);
          
    }
}
  
// This code is contributed by AnkThon

# Python3 implementation of the above approach
  
# Function to count minimum consecutive 
# removals of elements of the same type 
def minRemovals(A, N):
      
    # Sort the array
    A.sort()
  
    # Stores the maximum element 
    # present in the array 
    mx = A[N - 1]
  
    # stores the sum of array
    sum = 1
  
    # Calculate sum of array
    for i in range(0, N):
        sum += A[i]
  
    if ((sum - mx) >= mx):
        print(0, end = "")
    else:
        print(2 * mx - sum, end = "")
  
# Driver Code  
if __name__ == "__main__" :
      
    A = [ 3, 3, 2 ]
    N = len(A)
      
    # Function call 
    minRemovals(A, N) 
  
# This code is contributed by Virusbuddah

// C# implementation of the above approach
using System;
  
class GFG 
{
      
    // Function to count minimum consecutive
    // removals of elements of the same type
    static void minRemovals(int []A, int N)
    {
      
        // Sort the array
        Array.Sort(A);
      
        // Stores the maximum element
        // present in the array
        int mx = A[N - 1];
      
        // Stores sum of the array
        int sum = 1;
      
        // Calculate sum of the array
        for (int i = 0; i < N; i++)
        {
            sum += A[i];
        }
      
        if (sum - mx >= mx) 
        {
            Console.WriteLine(0);
        }
        else
        {
            Console.WriteLine(2 * mx - sum);
        }
    }
      
    // Driver Code
    public static void Main(String[] args) 
    {
        int []A = { 3, 3, 2 };
        int N = A.Length;
      
        // Function call
        minRemovals(A, N);      
    }
}
  
// This code is contributed by shikhasingrajput

<script>
  
// JavaScript program for above approach
  
    // Function to count minimum consecutive
    // removals of elements of the same type
    function minRemovals(A, N)
    {
       
        // Sort the array
        A.sort();
       
        // Stores the maximum element
        // present in the array
        let mx = A[N - 1];
       
        // Stores sum of the array
        let sum = 1;
       
        // Calculate sum of the array
        for (let i = 0; i < N; i++)
        {
            sum += A[i];
        }
       
        if (sum - mx >= mx) {
             document.write(0);
        }
        else {
             document.write(2 * mx - sum);
        }
    }
  
// Driver Code
  
     let A = [3, 3, 2 ];
        let N = A.length;
       
        // Function call
        minRemovals(A, N);
       
     // This code is contributed by avijitmondal1998.
</script>

0

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