Dado un número X y una array arr[] de longitud N que contiene los N números. La tarea es encontrar el número mínimo de operaciones requeridas para hacer que X no sea positivo. En una operación:
- Seleccione cualquier número Y de la array y reduzca X por Y .
- Luego haga Y = Y/2 (tome el valor mínimo si Y es impar).
- Si no es posible hacer que X no sea positivo, devuelva -1 .
Ejemplos:
Entrada: N = 3, arr[] = {3, 4, 12}, X = 25
Salida : 4
Explicación: Operación 1: Y=12, X se reduce a 13, Y se convierte en 6, arr[]: {3, 4 , 6}
Operación 2: Y = 6, X se reduce a 7, Y se convierte en 3, arr[]: {3, 4, 3}
Operación 3: Y = 4, X se reduce a 3, Y se convierte en 2, arr[]: {3, 2, 3}
Operación 4: Y = 3, X se reduce a 0, Y se convierte en 1, arr[]: {1, 2, 3}
El total de operaciones será 4.Entrada: N = 3, arr[] = {11, 11, 110}, X = 11011
Salida: -1
Explicación: Es imposible hacer que X no sea positivo
Enfoque : este problema se puede resolver usando max-heap ( priority queue ) basado en la siguiente idea:
Para minimizar la resta, es óptimo restar el valor máximo cada vez. Por esta razón, use un montón máximo para que los números de valor máximo permanezcan en la parte superior y realice la operación utilizando el elemento superior y siga verificando si el número se vuelve no positivo o no.
Siga la siguiente ilustración para una mejor comprensión.
Ilustración:
Considere arr[] = {3, 4, 12} y X = 25
Entonces max heap (digamos P ) = [3, 4, 12]
1er paso:
=> Elemento máximo (Y) = 12.
=> Restar 12 de 25. X = 25 – 12 = 13. Y = 12/2 = 6.
=> P = {3, 4, 6}.2do paso:
=> Elemento máximo (Y) = 6.
=> Restar 6 de 13. X = 13 – 6 = 7. Y = 6/2 = 3.
=> P = {3, 3, 4}.3er paso:
=> Elemento máximo (Y) = 4.
=> Reste 4 de 7. X = 7 – 4 = 3. Y = 4/2 = 2.
=> P = {2, 3, 3}.4to paso:
=> Elemento máximo (Y) = 3.
=> Restar 3 de 3. X = 3 – 3 = 0. Y = 3/2 = 1.
=> P = {1, 2, 3}.X no es positivo. Entonces operaciones requeridas = 4
Siga los pasos para resolver el problema:
- Cree un montón máximo (implementado por la cola de prioridad) y almacene todos los números en él.
- Realice lo siguiente hasta que la cola de prioridad no esté vacía y la X sea positiva.
- Utilice el número que tiene el valor máximo. Este será el número en la parte superior de la cola de prioridad.
- Elimine el número superior de la cola de prioridad y realice la operación como se indica en el problema.
- Después de realizar la operación, si Y es positivo, agréguelo nuevamente a la cola de prioridad.
- Incrementa la respuesta en 1 cada vez.
- Después de completar el proceso anterior, si X es positivo, entonces es imposible convertirlo en no positivo y, por lo tanto, devolver -1.
- De lo contrario, devuelve la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum operations
int minimumOperations(int N, int X,
vector<int> nums)
{
// Initialize answer as zero
int ans = 0;
// Create Max-Heap using
// Priority-queue
priority_queue<int> pq;
// Put all nums in the priority queue
for (int i = 0; i < N; i++)
pq.push(nums[i]);
// Execute the operation on num with
// max value until nums are left
// and X is positive
while (!pq.empty() and X > 0) {
if (pq.top() == 0)
break;
// Increment the answer everytime
ans++;
// num with maximum value
int num = pq.top();
// Removing the num
pq.pop();
// Reduce X's value and num's
// value as per the operation
X -= num;
num /= 2;
// If the num's value is positive
// insert back in the
// priority queue
if (num > 0)
pq.push(num);
}
// If X's value is positive then it
// is impossible to make X
// non-positive
if (X > 0)
return -1;
// Otherwise return the number of
// operations performed
return ans;
}
// Drivers code
int main()
{
int N = 3;
vector<int> nums = { 3, 4, 12 };
int X = 25;
// Function call
cout << minimumOperations(N, X, nums);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find minimum operations
public static int minimumOperations(int N, int X,
int nums[])
{
// Initialize answer as zero
int ans = 0;
// Create Max-Heap using
// Priority-queue
PriorityQueue<Integer> pq = new PriorityQueue<>(
Collections.reverseOrder());
// Put all nums in the priority queue
for (int i = 0; i < N; i++)
pq.add(nums[i]);
// Execute the operation on num with
// max value until nums are left
// and X is positive
while (!pq.isEmpty() && X > 0) {
if (pq.peek() == 0)
break;
// Increment the answer everytime
ans++;
// num with maximum value
int num = pq.peek();
// Removing the num
pq.poll();
// Reduce X's value and num's
// value as per the operation
X -= num;
num /= 2;
// If the num's value is positive
// insert back in the
// priority queue
if (num > 0)
pq.add(num);
}
// If X's value is positive then it
// is impossible to make X
// non-positive
if (X > 0)
return -1;
// Otherwise return the number of
// operations performed
return ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int nums[] = { 3, 4, 12 };
int X = 25;
// Function call
System.out.print(minimumOperations(N, X, nums));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code to implement the above approach # Function to find minimum operations def minimumOperations(N, X,nums): # Initialize answer as zero ans = 0 # Create Max-Heap using # Priority-queue pq = [] # Put all nums in the priority queue for i in range(N): pq.append(nums[i]) pq.sort() # Execute the operation on num with # max value until nums are left # and X is positive while (len(pq)>0 and X > 0): if (pq[len(pq)-1]== 0): break # Increment the answer everytime ans += 1 # num with maximum value num = pq[len(pq)-1] # Removing the num pq.pop() # Reduce X's value and num's # value as per the operation X -= num num //= 2 # If the num's value is positive # insert back in the # priority queue if (num > 0): pq.append(num) pq.sort() # If X's value is positive then it # is impossible to make X # non-positive if (X > 0): return -1 # Otherwise return the number of # operations performed return ans # Drivers code N = 3 nums = [ 3, 4, 12 ] X = 25 # Function call print(minimumOperations(N, X, nums)) # This code is contributed by shinjanpatra
C#
// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find minimum operations
public static int minimumOperations(int N, int X,
int[] nums)
{
// Initialize answer as zero
int ans = 0;
// Create Max-Heap using
// Priority-queue
List<int> pq = new List<int>();
// Put all nums in the priority queue
for (int i = 0; i < N; i++){
pq.Add(nums[i]);
pq.Sort();
pq.Reverse();
}
// Execute the operation on num with
// max value until nums are left
// and X is positive
while (pq.Count != 0 && X > 0) {
if (pq[0] == 0)
break;
// Increment the answer everytime
ans++;
// num with maximum value
int num = pq[0];
// Removing the num
pq.RemoveAt(0);
// Reduce X's value and num's
// value as per the operation
X -= num;
num /= 2;
// If the num's value is positive
// insert back in the
// priority queue
if (num > 0){
pq.Add(num);
pq.Sort();
pq.Reverse();
}
}
// If X's value is positive then it
// is impossible to make X
// non-positive
if (X > 0)
return -1;
// Otherwise return the number of
// operations performed
return ans;
}
// Driver Code
public static void Main()
{
int N = 3;
int[] nums = { 3, 4, 12 };
int X = 25;
// Function call
Console.WriteLine(minimumOperations(N, X, nums));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code to implement the above approach
// Function to find minimum operations
function minimumOperations(N, X,nums){
// Initialize answer as zero
let ans = 0
// Create Max-Heap using
// Priority-queue
let pq = []
// Put all nums in the priority queue
for(let i=0;i<N;i++)
pq.push(nums[i])
pq.sort((a,b)=>a-b)
// Execute the operation on num with
// max value until nums are left
// && X is positive
while (pq.length>0 && X > 0){
if (pq[pq.length-1]== 0)
break
// Increment the answer everytime
ans += 1
// num with maximum value
let num = pq[pq.length-1]
// Removing the num
pq.pop()
// Reduce X's value && num's
// value as per the operation
X -= num
num = Math.floor(num/2)
// If the num's value is positive
// insert back in the
// priority queue
if (num > 0)
pq.push(num)
pq.sort()
}
// If X's value is positive then it
// is impossible to make X
// non-positive
if (X > 0)
return -1
// Otherwise return the number of
// operations performed
return ans
}
// Drivers code
let N = 3
let nums = [ 3, 4, 12 ]
let X = 25
// Function call
document.write(minimumOperations(N, X, nums))
// This code is contributed by shinjanpatra
<script>
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ishankhandelwals y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA