Combinar los dos primeros elementos mínimos de la array hasta que todos los elementos sean mayores que K

Dada una array arr[] y un entero K , la tarea es encontrar el número de operaciones de combinación necesarias para que todos los elementos de la array sean mayores o iguales que K .

Proceso de fusión del elemento – 

New Element = 
   1 * (First Minimum element) + 
   2 * (Second Minimum element)

Ejemplos:  

Entrada: arr[] = {1, 2, 3, 9, 10, 12}, K = 7 
Salida:
Explicación: 
Después de la primera operación de combinación, los elementos 1 y 2 se eliminan 
y el elemento (1*1 + 2* 2 = 5) se inserta en la array 
{3, 5, 9, 10, 12} 
Después de la segunda operación de combinación, se eliminan los elementos 3 y 5, 
y el elemento (3*1 + 5*2 = 13) se inserta en la array 
{9, 10, 12, 13} 
Por lo tanto, se requieren 2 operaciones para que todos los elementos sean mayores que K.

Entrada: arr[] = {52, 96, 13, 37}, K = 10 
Salida:
Explicación: 
Todos los elementos de la array ya son mayores que K. 
Por lo tanto, no se requiere ninguna operación de fusión. 

Enfoque: la idea es usar Min-Heap para almacenar los elementos y luego fusionar los dos elementos mínimos de la array hasta que el elemento mínimo de la array sea mayor o igual a K. 

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

C++

// C++ implementation to merge the
// elements of the array until all
// the array element of the array
// greater than or equal to K
 
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to find the minimum
// operation required to merge
// elements of the array
int minOperations(int arr[], int K,
                          int size)
{
    int least, second_least,
       min_operations = 0,
       new_ele = 0, flag = 0;
 
    // Heap to store the elements
    // of the array and to extract
    // minimum elements of O(logN)
    priority_queue<int, vector<int>,
                 greater<int> > heap;
                  
    // Loop to push all the elements
    // of the array into heap
    for (int i = 0; i < size; i++) {
        heap.push(arr[i]);
    }
     
    // Loop to merge the minimum
    // elements until there is only
    // all the elements greater than K
    while (heap.size() != 1) {
         
        // Condition to check minimum
        // element of the array is
        // greater than the K
        if (heap.top() >= K) {
            flag = 1;
            break;
        }
         
        // Merge the two minimum
        // elements of the heap
        least = heap.top();
        heap.pop();
        second_least = heap.top();
        heap.pop();
        new_ele = (1 * least) +
            (2 * second_least);
        min_operations++;
        heap.push(new_ele);
    }
    if (heap.top() >= K) {
        flag = 1;
    }
    if (flag == 1) {
        return min_operations;
    }
    return -1;
}
 
// Driver Code
int main()
{
    int N = 6, K = 7;
    int arr[] = { 1, 2, 3, 9, 10, 12 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << minOperations(arr, K, size);
    return 0;
}

Java

// Java implementation to merge the
// elements of the array until all
// the array element of the array
// greater than or equal to K
import java.util.Collections;
import java.util.PriorityQueue;
 
class GFG{
 
// Function to find the minimum
// operation required to merge
// elements of the array
static int minOperations(int arr[], int K,
                         int size)
{
    int least, second_least,
        min_operations = 0,
        new_ele = 0, flag = 0;
 
    // Heap to store the elements
    // of the array and to extract
    // minimum elements of O(logN)
    PriorityQueue<Integer> heap = new PriorityQueue<>();
     
    // priority_queue<int, vector<int>,
    // greater<int> > heap;
 
    // Loop to push all the elements
    // of the array into heap
    for(int i = 0; i < size; i++)
    {
        heap.add(arr[i]);
    }
 
    // Loop to merge the minimum
    // elements until there is only
    // all the elements greater than K
    while (heap.size() != 1)
    {
         
        // Condition to check minimum
        // element of the array is
        // greater than the K
        if (heap.peek() >= K)
        {
            flag = 1;
            break;
        }
 
        // Merge the two minimum
        // elements of the heap
        least = heap.poll();
        second_least = heap.poll();
        new_ele = (1 * least) +
                  (2 * second_least);
        min_operations++;
        heap.add(new_ele);
    }
    if (heap.peek() >= K)
    {
        flag = 1;
    }
    if (flag == 1)
    {
        return min_operations;
    }
    return -1;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 6, K = 7;
    int arr[] = { 1, 2, 3, 9, 10, 12 };
    int size = arr.length;
     
    System.out.println(minOperations(arr, K, size));
}
}
 
// This code is contributed by sanjeev2552

Python3

# Python3 implementation to merge the
# elements of the array until all
# the array element of the array
# greater than or equal to K
# importing heapq module as hq
 
import heapq as hq
 
# Function to find the minimum
# operation required to merge
# elements of the array
 
 
def minOperations(arr, K, size):
 
    least, second_least = 0, 0
    min_operations = 0
    new_ele, flag = 0, 0
    # Heap to store the elements
    # of the array and to extract
    # minimum elements of O(logN)
    hq.heapify(arr)
    # Loop to merge the minimum
    # elements until there is only
    # all the elements greater than K
    while len(arr) > 0:
        # Condition to check minimum
        # element of the array is
        # greater than the K
        if arr[0] >= K:
            flag = 1
            break
        # Merge the two minimum
        # elements of the heap
        least = arr[0]
        arr[0] = arr[-1]
        # reducing the size of the heap
        #it is O(1) time operation..
        arr.pop()
        # maintaining the min heap property
        #O(log n) time needed for heapifying
        hq.heapify(arr)
        # extracting the second_least element
        # from the heap
        second_least = arr[0]
        arr[0] = arr[-1]
        arr.pop()
        # creating the new_ele
        new_ele = least+2*second_least
        # increasing the min_operations
        min_operations += 1
        # inserting new_ele back to heap
        arr.append(new_ele)
        # now again maintaining the min heap property again
        # using the heapify function
        hq.heapify(arr)
    if arr[0] >= K:
        flag = 1
    if flag == 1:
        return min_operations
    return -1
 
 
# Driver code
K = 7
arr = [1, 2, 3, 9, 10, 12]
size = len(arr)
print(minOperations(arr, K, size))
'''Code is written by Rajat Kumar'''

C#

// C# implementation to merge the
// elements of the array until all
// the array element of the array
// greater than or equal to K
using System;
using System.Collections.Generic;
class GFG
{
 
  // Function to find the minimum
  // operation required to merge
  // elements of the array
  static int minOperations(int[] arr, int K, int size)
  {
    int least, second_least, min_operations = 0,
    new_ele = 0, flag = 0;
 
    // Heap to store the elements
    // of the array and to extract
    // minimum elements of O(logN)
    List<int> heap = new List<int>();
 
    // priority_queue<int, vector<int>,
    // greater<int> > heap;
 
    // Loop to push all the elements
    // of the array into heap
    for(int i = 0; i < size; i++)
    {
      heap.Add(arr[i]);
    }
    heap.Sort();
    heap.Reverse();
 
    // Loop to merge the minimum
    // elements until there is only
    // all the elements greater than K
    while(heap.Count != 1)
    {
 
      // Condition to check minimum
      // element of the array is
      // greater than the K
      if(heap[heap.Count - 1] >= K)
      {
        flag = 1;
        break;
      }
 
      // Merge the two minimum
      // elements of the heap
      least = heap[heap.Count - 1];
      heap.RemoveAt(heap.Count - 1);
      second_least = heap[heap.Count - 1];
      heap.RemoveAt(heap.Count - 1);
      new_ele = (1 * least) +(2 * second_least);
      min_operations++;
      heap.Add(new_ele);
      heap.Sort();
      heap.Reverse();          
    }
    if(heap[heap.Count - 1] >= K)
    {
      flag = 1;
    }
    if(flag == 1)
    {
      return min_operations;
    }
    return -1;       
  }
 
  // Driver Code
  static public void Main ()
  {
    int K = 7;
    int[] arr = { 1, 2, 3, 9, 10, 12 };
    int size = arr.Length;
    Console.WriteLine(minOperations(arr, K, size));
  }
}
 
// This code is contributed by avanitrachhadiya2155

Javascript

<script>
// Javascript implementation to merge the
// elements of the array until all
// the array element of the array
// greater than or equal to K
 
// Function to find the minimum
// operation required to merge
// elements of the array
function  minOperations(arr,K,size)
{
    let least, second_least,
        min_operations = 0,
        new_ele = 0, flag = 0;
  
    // Heap to store the elements
    // of the array and to extract
    // minimum elements of O(logN)
    let heap = [];
      
    // priority_queue<int, vector<int>,
    // greater<int> > heap;
  
    // Loop to push all the elements
    // of the array into heap
    for(let i = 0; i < size; i++)
    {
        heap.push(arr[i]);
    }
  
    // Loop to merge the minimum
    // elements until there is only
    // all the elements greater than K
    while (heap.length != 1)
    {
          
        // Condition to check minimum
        // element of the array is
        // greater than the K
        if (heap[0] >= K)
        {
            flag = 1;
            break;
        }
  
        // Merge the two minimum
        // elements of the heap
        least = heap.shift();
        second_least = heap.shift();
        new_ele = (1 * least) +
                  (2 * second_least);
        min_operations++;
        heap.push(new_ele);
    }
    if (heap[0] >= K)
    {
        flag = 1;
    }
    if (flag == 1)
    {
        return min_operations;
    }
    return -1;
}
 
// Driver Code
let N = 6, K = 7;
let arr=[1, 2, 3, 9, 10, 12];
let size = arr.length;
document.write(minOperations(arr, K, size));
 
 
// This code is contributed by patel2127
</script>
Producción: 

2

 

Complejidad de tiempo: la complejidad de los algoritmos anteriores está determinada por uno por el ciclo while y segundo por la operación heapify. El tiempo que tarda el ciclo while es O(N) y dentro del mismo ciclo while se usa la operación heapify() que tomará 

O(Log n) tiempo, por lo que la complejidad total del tiempo será O(N* Log N).

Complejidad del espacio: se requeriría espacio O(N) para almacenar elementos en el montón. 

Publicación traducida automáticamente

Artículo escrito por Sourav_35 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 *