Operaciones mínimas para reducir Array a 0 restando el elemento más pequeño de un par repetidamente

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N , la tarea es encontrar el número mínimo de operaciones requeridas para hacer que todos los elementos de la array sean cero. En una operación, seleccione un par de elementos y reste el elemento más pequeño de ambos elementos en la array.

Ejemplo:

Entrada: arr[] = {1, 2, 3, 4}
Salida: 3
Explicación: Elija los elementos en la siguiente secuencia:
Operación 1: Elija elementos en los índices {3, 2}: arr[]={1, 2, 0, 1}
Operación 2: Seleccionar elementos en los índices {1, 3}: arr[]={1, 1, 0, 0}
Operación 3: Seleccionar elementos en los índices {2, 1}: arr[]={0, 0, 0, 0}

Entrada: arr[] = {2, 2, 2, 2}
Salida: 2

 

Enfoque:   este problema se puede resolver utilizando una cola de prioridad . Para resolver el siguiente problema, siga los pasos a continuación:

  1. Recorra la array y empuje todos los elementos que son mayores que 0, en la cola de prioridad.
  2. Cree una variable op para almacenar el número de operaciones e inicialícela con 0.
  3. Ahora, itera sobre la cola de prioridad pq ​​hasta que su tamaño sea mayor que uno en cada iteración:
    • Incrementa el valor de la variable op.
    • Luego seleccione los dos elementos superiores, digamos p y q para aplicar la operación dada.
    • Después de aplicar la operación, un elemento definitivamente se convertirá en 0. Empuje el otro de vuelta a la cola de prioridad si es mayor que cero.
  4. Repita la operación anterior hasta que la cola de prioridad se quede vacía.
  5. Imprimir op , como la respuesta a esta pregunta.

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of operations required to make all
// array elements zero
int setElementstoZero(int arr[], int N)
{
 
    // Create a priority queue
    priority_queue<int> pq;
 
    // Variable to store the number
    // of operations
    int op = 0;
 
    for (int i = 0; i < N; i++) {
        if (arr[i] > 0) {
            pq.push(arr[i]);
        }
    }
 
    // Iterate over the priority queue
    // till size is greater than 1
    while (pq.size() > 1) {
        // Increment op by 1
        op += 1;
 
        auto p = pq.top();
        pq.pop();
        auto q = pq.top();
        pq.pop();
 
        // If the element is still greater
        // than zero again push it again in pq
        if (p - q > 0) {
            pq.push(p);
        }
    }
 
    // Return op as the answer
    return op;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << setElementstoZero(arr, N);
 
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
class CustomComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2)
    {
        int value = number1.compareTo(number2);
       
        // elements are sorted in reverse order
        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}
class GFG
{
   
    // Function to find the minimum number
    // of operations required to make all
    // array elements zero
    static int setElementstoZero(int arr[], int N)
    {
       
        // Create a priority queue
        PriorityQueue<Integer> pq
            = new PriorityQueue<Integer>(
                new CustomComparator());
       
        // Variable to store the number
        // of operations
        int op = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] > 0) {
                pq.add(arr[i]);
            }
        }
        // Iterate over the priority queue
        // till size is greater than 1
        while (pq.size() > 1)
        {
           
            // Increment op by 1
            op = op + 1;
            Integer p = pq.poll();
            Integer q = pq.poll();
           
            // If the element is still greater
            // than zero again push it again in pq
            if (p - q > 0) {
                pq.add(p);
            }
        }
       
        // Return op as the answer
        return op;
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 3, 4 };
        int N = arr.length;
        System.out.println(setElementstoZero(arr, N));
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python program for the above approach
 
# Function to find the minimum number
# of operations required to make all
# array elements zero
def setElementstoZero(arr, N):
 
    # Create a priority queue
    pq = []
 
    # Variable to store the number
    # of operations
    op = 0
 
    for i in range(N):
        if (arr[i] > 0):
            pq.append(arr[i])
 
    pq.sort()
 
    # Iterate over the priority queue
    # till size is greater than 1
    while (len(pq) > 1):
        # Increment op by 1
        op += 1
 
        p = pq[len(pq) - 1]
        pq.pop()
        q = pq[len(pq)-1]
        pq.pop()
 
        # If the element is still greater
        # than zero again push it again in pq
        if (p - q > 0):
            pq.append(p)
        pq.sort()
 
    # Return op as the answer
    return op
 
 
# Driver Code
arr = [1, 2, 3, 4]
N = len(arr)
print(setElementstoZero(arr, N))
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
public class GFG {
 
  // Function to find the minimum number
  // of operations required to make all
  // array elements zero
  static int setElementstoZero(int[] arr, int N)
  {
 
    // Create a priority queue
    List<int> pq = new List<int>();
 
    // Variable to store the number
    // of operations
    int op = 0;
    for (int i = 0; i < N; i++) {
      if (arr[i] > 0) {
        pq.Add(arr[i]);
      }
    }
     
    // Iterate over the priority queue
    // till size is greater than 1
    while (pq.Count > 1) {
      pq.Sort();
      pq.Reverse();
       
      // Increment op by 1
      op = op + 1;
      int p = pq[0];
 
      int q = pq[1];
      pq.RemoveRange(0, 2);
 
      // If the element is still greater
      // than zero again push it again in pq
      if (p - q > 0) {
        pq.Add(p);
      }
    }
 
    // Return op as the answer
    return op;
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int[] arr = { 1, 2, 3, 4 };
    int N = arr.Length;
    Console.WriteLine(setElementstoZero(arr, N));
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to find the minimum number
// of operations required to make all
// array elements zero
function setElementstoZero(arr, N)
{
 
    // Create a priority queue
    var pq = [];
 
    // Variable to store the number
    // of operations
    var op = 0;
 
    for(var i = 0; i < N; i++) {
        if (arr[i] > 0) {
            pq.push(arr[i]);
        }
    }
 
    pq.sort((a,b) => a-b);
 
    // Iterate over the priority queue
    // till size is greater than 1
    while (pq.length > 1) {
        // Increment op by 1
        op += 1;
         
        var p = pq[pq.length-1];
        pq.pop();
        var q = pq[pq.length-1];
        pq.pop();
 
        // If the element is still greater
        // than zero again push it again in pq
        if (p - q > 0) {
            pq.push(p);
        }
        pq.sort((a,b) => a-b);
    }
 
    // Return op as the answer
    return op;
}
 
// Driver Code
var arr = [ 1, 2, 3, 4 ];
var N = arr.length;
document.write(setElementstoZero(arr, N));
 
// This code is contributed by rutvik_56.
</script>
Producción

3

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

Publicación traducida automáticamente

Artículo escrito por samim2000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *