Convierta el Array dado a 0 reduciendo los elementos por pares con cualquier valor positivo

Dada una array arr[] de tamaño N , la tarea es encontrar el número de operaciones para convertir los elementos de la array a cero al disminuir el valor de los elementos de la array en pares por cualquier valor positivo . Si los elementos de la array no se pueden convertir a 0, devuelve -1 .

Entrada: arr[] = {3, 2}
Salida: -1
Explicación: Todos los elementos de la array no se pueden convertir a 0
Entrada: arr[] = {5, 4, 3}
Salida: 12
Explicación: Resta 1 del par (4, 3) obtenemos {5, 3, 2}, restamos 3 de (5, 3) obtenemos {2, 0, 2}, Restamos 2 del par (2, 2) obtenemos {0, 0, 0 }

Acercarse:La tarea se puede resolver almacenando todos los elementos de una array en una cola de prioridad . Luego, debemos elegir un par de los dos elementos más grandes de la cola y restarles 1 hasta que solo quede un elemento positivo o ninguno .
Siga los pasos a continuación para resolver el problema:

• Almacenar elementos en la cola de prioridad
• Tome un ciclo while hasta que el tamaño de la cola de prioridad sea mayor o igual a 2, y en cada iteración:-
  1. Extrae los dos primeros elementos y guárdalos en las variables ele1 y ele2 
  2. Decrementa ele1 y ele2 con 1. Si alguno de ellos sigue siendo mayor que cero, vuélvelo a colocar en la cola.
• Si la cola está vacía, imprima el número de operaciones necesarias, de lo contrario, -1

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether
// all element of vector can
// become zero after the operations
void gfg(vector<int>& v)
{
 
    // Priroty queue to store
    // elements of vector v
    priority_queue<int> q;
 
    // Loop to store elements
    // in priroty queue
    for (auto x : v) {
        q.push(x);
    }
 
    // Stores the number
    // of operations needed
    int cnt = 0;
    while (q.size() >= 2) {
 
        // Variable to store greatest
        // element of priority queue
        int ele1 = q.top();
        q.pop();
 
        // Variable to store second greatest
        // element of priority queue
        int ele2 = q.top();
        q.pop();
 
        // Decrementing both by 1
        ele1--;
        ele2--;
        cnt += 2;
 
        // If elements are greater
        // then zero it is again
        // stored in the priority queue
        if (ele1) {
            q.push(ele1);
        }
        if (ele2) {
            q.push(ele2);
        }
    }
 
    if (q.size() == 0)
        cout << cnt << endl;
    else
        cout << -1;
}
 
// Driver code
int main()
{
 
    vector<int> v = { 5, 3, 4 };
    gfg(v);
}

// Java program for the above approach
import java.util.*;
class GFG{
 
  // Function to check whether
  // all element of vector can
  // become zero after the operations
  static void gfg(int[] v)
  {
 
    // Priroty queue to store
    // elements of vector v
    PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
 
    // Loop to store elements
    // in priroty queue
    for (int x : v) {
      q.add(x);
    }
 
    // Stores the number
    // of operations needed
    int cnt = 0;
    while (q.size() >= 2) {
 
      // Variable to store greatest
      // element of priority queue
      int ele1 = q.peek();
      q.remove();
 
      // Variable to store second greatest
      // element of priority queue
      int ele2 = q.peek();
      q.remove();
 
      // Decrementing both by 1
      ele1--;
      ele2--;
      cnt += 2;
 
      // If elements are greater
      // then zero it is again
      // stored in the priority queue
      if (ele1>0) {
        q.add(ele1);
      }
      if (ele2>0) {
        q.add(ele2);
      }
    }
 
    if (q.size() == 0)
      System.out.print(cnt +"\n");
    else
      System.out.print(-1);
  }
 
  // Driver code
  public static void main(String[] args)
  {
 
    int[] v = { 5, 3, 4 };
    gfg(v);
  }
}
 
// This code is contributed by shikhasingrajput

# Python code for the above approach
from queue import PriorityQueue
 
# Function to check whether
# all element of vector can
# become zero after the operations
def gfg(v):
 
    # Priroty queue to store
    # elements of vector v
    q = PriorityQueue()
 
    # Loop to store elements
    # in priroty queue
    for i in range(len(v)):
        q.put(-1 * v[i])
 
    # Stores the number
    # of operations needed
    cnt = 0
    while (q.qsize() >= 2):
 
        # Variable to store greatest
        # element of priority queue
        ele1 = -1 * q.get()
 
        # Variable to store second greatest
        # element of priority queue
        ele2 = -1 * q.get()
        # Decrementing both by 1
        ele1 = ele1-1
        ele2 = ele2-1
        cnt = cnt + 2
 
        # If elements are greater
        # then zero it is again
        # stored in the priority queue
        if ele1 > 0:
            q.put(-1 * ele1)
        if ele2 > 0:
            q.put(-1 * ele2)
 
    if q.qsize() == 0:
        print(cnt)
    else:
        print(-1)
 
# Driver code
v = [5, 3, 4]
gfg(v)
 
# This code is contributed by Potta Lokesh

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
  // Function to check whether
  // all element of vector can
  // become zero after the operations
  static void gfg(int[] v)
  {
 
    // Priroty queue to store
    // elements of vector v
    List<int> q = new List<int>();
 
    // Loop to store elements
    // in priroty queue
    foreach(int x in v) {
      q.Add(x);
    }
 
    // Stores the number
    // of operations needed
    int cnt = 0;
    while (q.Count >= 2) {
 
      // Variable to store greatest
      // element of priority queue
      int ele1 = q[0];
      q.RemoveAt(0);
 
      // Variable to store second greatest
      // element of priority queue
      int ele2 = q[0];
      q.RemoveAt(0);
 
      // Decrementing both by 1
      ele1--;
      ele2--;
      cnt += 2;
 
      // If elements are greater
      // then zero it is again
      // stored in the priority queue
      if (ele1 > 0) {
        q.Add(ele1);
      }
      if (ele2 > 0) {
        q.Add(ele2);
      }
    }
 
    if (q.Count == 0)
      Console.Write(cnt +"\n");
    else
      Console.Write(-1);
  }
 
  // Driver code
  public static void Main(String[] args)
  {
 
    int[] v = { 5, 3, 4 };
    gfg(v);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
// javascript program for the above approach
 
    // Function to check whether
    // all element of vector can
    // become zero after the operations
    function gfg(v) {
 
        // Priroty queue to store
        // elements of vector v
         q = [];
 
        // Loop to store elements
        // in priroty queue
        for (x of v) {
            q.push(x);
                 
        }
q.sort((a, b)=>b - a);
 
        // Stores the number
        // of operations needed
        var cnt = 0;
        while (q.length >= 2) {
 
            // Variable to store greatest
            // element of priority queue
            var ele1 = q[0];
            q.splice(0, 1);
 
            // Variable to store second greatest
            // element of priority queue
            var ele2 = q[0];
        q.splice(0, 1);
 
            // Decrementing both by 1
            ele1 -= 1;
            ele2 -=1;
            cnt += 2;
 
            // If elements are greater
            // then zero it is again
            // stored in the priority queue
            if (ele1 > 0) {
                q.push(ele1);
            }
            if (ele2 > 0) {
                q.push(ele2);
            }
        }
 
        if (q.length == 0)
            document.write(cnt + "\n");
        else
            document.write(-1);
    }
 
    // Driver code
        var v = [ 5, 3, 4 ];
        gfg(v);
 
// This code is contributed by umadevi9616
</script>

12

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)