Given a number X, and an array arr[] of length N containing the N numbers. The task is to find the minimum number of operations required to make X non-positive. In one operation:
- Select any one number Y from the array and reduce X by Y.
- Then make Y = Y/2 (take floor value if Y is odd).
- If it is not possible to make X non-positive, return -1.
Examples:
Input: N = 3, arr[] = {3, 4, 12}, X = 25
Output: 4
Explanation: Operation 1: Y=12, X reduces to 13, Y becomes 6, arr[]: {3, 4, 6}
Operation 2: Y = 6, X reduces to 7, Y becomes 3, arr[]: {3, 4, 3}
Operation 3: Y = 4, X reduces to 3, Y becomes 2, arr[]: {3, 2, 3}
Operation 4: Y = 3, X reduces to 0, Y becomes 1, arr[]: {1, 2, 3}
Total operations will be 4.Input: N = 3, arr[] = {11, 11, 110}, X = 11011
Output: -1
Explanation: It is impossible to make X non-positive
Approach: This problem can be solved using max-heap (priority queue) based on the following idea:
To minimize subtraction, it is optimal to subtract the maximum value each time. For this reason use a max-heap so that the maximum value numbers remain on top and perform the operation using the topmost element and keep checking if the number becomes non-positive or not.
Follow the below illustration for a better understanding.
Illustration:
Consider arr[] = {3, 4, 12} and X = 25
So max heap (say P) = [3, 4, 12]
1st step:
=> Maximum element (Y) = 12.
=> Subtract 12 from 25. X = 25 – 12 = 13. Y = 12/2 = 6.
=> P = {3, 4, 6}.2nd step:
=> Maximum element (Y) = 6.
=> Subtract 6 from 13. X = 13 – 6 = 7. Y = 6/2 = 3.
=> P = {3, 3, 4}.3rd step:
=> Maximum element (Y) = 4.
=> Subtract 4 from 7. X = 7 – 4 = 3. Y = 4/2 = 2.
=> P = {2, 3, 3}.4th step:
=> Maximum element (Y) = 3.
=> Subtract 3 from 3. X = 3 – 3 = 0. Y = 3/2 = 1.
=> P = {1, 2, 3}.X is non-positive. So operations required = 4
Follow the steps to solve the problem:
- Create a max-heap (implemented by priority queue)and store all the numbers in it.
- Perform the following until the priority queue is not empty and the X is positive.
- Use the number having the maximum value. This will be the number on top of the priority queue.
- Remove the top number from the priority queue and perform the operation as stated in the problem.
- After performing the operation, if Y is positive add it back to the priority queue.
- Increment the answer by 1 every time.
- After the completion of the above process, if X is positive then it is impossible to make it non-positive and thus return -1.
- Otherwise, return the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum operationsint 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 codeint 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 approachimport 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# importing heapq module for implementing max heapimport heapq as hq# Function to find minimum operationsdef minimumOperations(N, X, nums): # Initialize answer as zero ans = 0 # assigning nums to pq pq = nums # converting pq to max heap # using heapq module hq._heapify_max(pq) # 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 # first element of max heap # contains maximum value num = pq[0] # deleting one maximum element # from max heap pq[0] = pq[-1] pq.pop() # again converting current pq # to max heap in O(n) time hq._heapify_max(pq) # 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) hq._heapify_max(pq) # 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 codeN = 3nums = [3, 4, 12]X = 25# Function callprint(minimumOperations(N, X, nums)) |
C#
// C# code for the above approachusing 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 operationsfunction 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 codelet N = 3let nums = [ 3, 4, 12 ]let X = 25// Function calldocument.write(minimumOperations(N, X, nums))// This code is contributed by shinjanpatra<script> |
4
Time Complexity: O(N * log N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!