Minimum operations to make X non-positive

Given a number X, and an array of length N containing the N numbers. Find the minimum number of operations required to make X non-positive.

In one operation, you can select any one number Y from the array and reduce X by Y. Then Y is halved (take floor value in case Y is odd).

If it is not possible to make X non-positive, return -1.

Examples :

Input : N = 3       array[] ={3,4,12}      X = 25
Output : 4
Explanation :
Operation 1: Y=12,   X reduces to 13,  Y becomes 6,     array[]:
{3,4,6}
Operation 2: Y=6,    X reduces to 7,   Y becomes 3,       array[]:
{3,4,3}
Operation 3: Y=4,    X reduces to 3, Y becomes 2,       array[]:
{3,2,3}
Operation 4: Y=3,    X reduces to 0,   Y becomes 1,     array[]:
{1,2,3}
Total operations will be 4.

Input : N = 3     array[] = {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).

Create a max-heap using a max priority queue and store all the numbers in it.
Always use the number having the maximum value. This will be the number on top of the priority queue.
Remove(pop) 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.
Repeat the process until the priority queue is not empty and the X is positive and 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.

Implementation :

#include <bits/stdc++.h>
using namespace std;

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
    // make X non-positive
    if (X > 0)
        return -1;

    // Otherwise return the number of operations performed
    return ans;
}

int main()
{
    int n = 3;
    vector<int> nums = { 3, 4, 12 };
    int x = 25;

    cout << minimumOperations(n, x, nums) << endl;
    return 0;
}

Output :

Time Complexity: O(NlogN)
Auxiliary Space : O(N)

Minimum operations to make X non-positive using a max heap

Implementation :

Related tutorials