Dada una array de longitud N . La tarea es convertirlo en una secuencia en la que todos los elementos sean mayores o iguales a K. La única operación permitida es tomar dos elementos más pequeños de la secuencia y reemplazarlos por su MCM. Encuentre el número mínimo de operaciones requeridas.
Si es imposible obtener tal array, imprima -1.
Ejemplos:
Entrada: N = 4, K = 3, arr=[1 4 5 5]
Salida: 1
MCM de 1 y 4 es 4, por lo tanto, reemplace (1,4) con 4.
Ahora la array se convierte en [4,4,5] .
Cada elemento en esta array es mayor o igual a K.
El número de operaciones requeridas es igual a 1.
Entrada: N = 5, K = 8, arr=[4,4,4,4,4]
Salida: -1
It no es posible convertir la array dada.
Acercarse:
- La idea es usar una cola de prioridad (montón mínimo) que pueda manejar la operación de eliminación e inserción en el tiempo de registro (N).
- El caso imposible surgirá cuando el número de elementos en la cola de prioridad sea menor a 2. La respuesta es igual a -1 en este caso.
- De lo contrario, tome dos elementos de la parte superior de la cola y reemplácelos por su LCM.
- Haga esto hasta que el número más pequeño que esté en la parte superior de la cola sea menor que K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// C++ function to get
// minimum operation needed
int FindMinOperation(int a[], int n, int k)
{
// The priority queue holds a minimum
// element in the top position
priority_queue<int, vector<int>,
greater<int> > Q;
for (int i = 0; i < n; i++)
// push value one by one
// from the given array
Q.push(a[i]);
// store count of minimum operation needed
int ans = 0;
while (1) {
// All elements are now >= k
if (Q.top() >= k)
break;
// It is impossible to make as there are
// no sufficient elements available
if (Q.size() < 2)
return -1;
// Take two smallest elements and
// replace them by their LCM
// first smallest element
int x = Q.top();
Q.pop();
// Second smallest element
int y = Q.top();
Q.pop();
int z = (x * y) / __gcd(x, y);
Q.push(z);
// Increment the count
ans++;
}
return ans;
}
// Driver Code
int main()
{
int a[] = { 3, 5, 7, 6, 8 };
int k = 8;
int n = sizeof(a) / sizeof(a[0]);
cout << FindMinOperation(a, n, k);
}
Java
// Java implementation of above approach
import java.util.PriorityQueue;
class GFG
{
// Function to calculate gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Java function to get
// minimum operation needed
static int FindMinOperation(int[] a, int n, int k)
{
// The priority queue holds a minimum
// element in the top position
PriorityQueue<Integer> Q = new PriorityQueue<>();
for (int i = 0; i < n; i++)
// push value one by one
// from the given array
Q.add(a[i]);
// store count of minimum operation needed
int ans = 0;
while (true)
{
// All elements are now >= k
if (Q.peek() >= k)
break;
// It is impossible to make as there are
// no sufficient elements available
if (Q.size() < 2)
return -1;
// Take two smallest elements and
// replace them by their LCM
// first smallest element
int x = Q.peek();
Q.poll();
// Second smallest element
int y = Q.peek();
Q.poll();
int z = (x * y) / gcd(x, y);
Q.add(z);
// Increment the count
ans++;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int[] a = { 3, 5, 7, 6, 8 };
int k = 8;
int n = a.length;
System.out.println(FindMinOperation(a, n, k));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of above approach # Function to calculate gcd of two numbers def gcd(a, b) : if (a == 0) : return b return gcd(b % a, a) # function to get # minimum operation needed def FindMinOperation(a, n, k) : # The priority queue holds a minimum # element in the top position Q = [] for i in range(0, n) : # push value one by one # from the given array Q.append(a[i]) Q.sort() # store count of minimum operation needed ans = 0 while (True) : # All elements are now >= k if (Q[0] >= k) : break # It is impossible to make as there are # no sufficient elements available if (len(Q) < 2) : return -1 # Take two smallest elements and # replace them by their LCM # first smallest element x = Q[0] Q.pop(0) # Second smallest element y = Q[0] Q.pop(0) z = (x * y) // gcd(x, y) Q.append(z) Q.sort() # Increment the count ans += 1 return ans # Driver code a = [ 3, 5, 7, 6, 8 ] k = 8 n = len(a) print(FindMinOperation(a, n, k)) # This code is contributed by divyesh0720219.
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to calculate gcd of two numbers
static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// C# function to get
// minimum operation needed
static int FindMinOperation(int[] a, int n, int k)
{
// The priority queue holds a minimum
// element in the top position
List<int> Q = new List<int>();
for (int i = 0; i < n; i++)
// push value one by one
// from the given array
Q.Add(a[i]);
Q.Sort();
// store count of minimum operation needed
int ans = 0;
while (true)
{
// All elements are now >= k
if (Q[0] >= k)
break;
// It is impossible to make as there are
// no sufficient elements available
if (Q.Count < 2)
return -1;
// Take two smallest elements and
// replace them by their LCM
// first smallest element
int x = Q[0];
Q.RemoveAt(0);
// Second smallest element
int y = Q[0];
Q.RemoveAt(0);
int z = (x * y) / gcd(x, y);
Q.Add(z);
Q.Sort();
// Increment the count
ans++;
}
return ans;
}
// Driver code
static void Main()
{
int[] a = { 3, 5, 7, 6, 8 };
int k = 8;
int n = a.Length;
Console.WriteLine(FindMinOperation(a, n, k));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of above approach
// Function to calculate gcd of two numbers
function gcd(a, b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// function to get
// minimum operation needed
function FindMinOperation(a, n, k)
{
// The priority queue holds a minimum
// element in the top position
let Q = [];
for (let i = 0; i < n; i++)
// push value one by one
// from the given array
Q.push(a[i]);
Q.sort(function(a, b){return a - b});
// store count of minimum operation needed
let ans = 0;
while (true)
{
// All elements are now >= k
if (Q[0] >= k)
break;
// It is impossible to make as there are
// no sufficient elements available
if (Q.length < 2)
return -1;
// Take two smallest elements and
// replace them by their LCM
// first smallest element
let x = Q[0];
Q.shift();
// Second smallest element
let y = Q[0];
Q.shift();
let z = parseInt((x * y) / gcd(x, y), 10);
Q.push(z);
Q.sort(function(a, b){return a - b});
// Increment the count
ans++;
}
return ans;
}
let a = [ 3, 5, 7, 6, 8 ];
let k = 8;
let n = a.length;
document.write(FindMinOperation(a, n, k));
</script>
Producción:
2
Complejidad de tiempo: O (NlogN)