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: 2
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: 0
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.