Tuesday, November 28, 2023
HomeSoftware DevelopmentReduce subtraction of Array parts to make X at most 0

# Reduce subtraction of Array parts to make X at most 0

Given a quantity X, and an array arr[] of size N containing the N numbers. The duty is to seek out the minimal variety of operations required to make X non-positive. In a single operation:

• Choose anyone quantity Y from the array and cut back X by Y
• Then make Y = Y/2 (take ground worth if Y is odd).
• If it’s not attainable to make X non-positive, return -1.

Examples:

Enter: N = 3, arr[] = {3, 4, 12}, X = 25
Output:  4
Clarification: Operation 1: Y=12,   X reduces to 13,  Y turns into 6, arr[]: {3, 4, 6}
Operation 2: Y = 6, X reduces to 7, Y turns into 3, arr[]: {3, 4, 3}
Operation 3: Y = 4, X reduces to three, Y turns into 2, arr[]: {3, 2, 3}
Operation 4: Y = 3, X reduces to 0, Y turns into 1, arr[]: {1, 2, 3}
Complete operations shall be 4.

Enter:  N = 3, arr[] = {11, 11, 110}, X = 11011
Output: -1
Clarification: It’s inconceivable to make X non-positive

Strategy: This drawback may be solved utilizing max-heap (precedence queue) based mostly on the next concept:

To minimze subtraction, it’s optimum to subtract the utmost worth every time. Fo rthis reaseon use a max-heap in order that the utmost worth numbers stay on high and carry out the operation utilizing the topmost component and hold checking if the quantity turns into non-positive or not.

Observe the under illustration for a greater understanding.

Illustration:

Take into account arr[] = {3, 4, 12} and X = 25

So max heap (say P) = [3, 4, 12]

1st step:
=> Most component (Y) = 12.
=> Subtract 12 from 25. X = 25 – 12 = 13. Y = 12/2 = 6.
=> P = {3, 4, 6}.

2nd step:
=> Most component (Y) = 6.
=> Subtract 6 from 13. X = 13 – 6 = 7. Y = 6/2 = 3.
=> P = {3, 3, 4}.

third step:
=> Most component (Y) = 4.
=> Subtract 4 from 7. X = 7 – 4 = 3. Y = 4/2 = 2.
=> P = {2, 3, 3}.

4th step:
=> Most component (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

Observe the steps to resolve the issue:

• Create a max-heap (applied by precedence queue)and retailer all of the numbers in it.
• Carry out the next till the precedence queue isn’t empty and the X is constructive.
• Use the quantity having the utmost worth. This would be the quantity on high of the precedence queue.
• Take away the highest quantity from the precedence queue and carry out the operation as acknowledged in the issue.
• After performing the operation, if Y is constructive add it again to the precedence queue.
• Increment the reply by 1 each time.
• After the completion of the above course of, if X is constructive then it’s inconceivable to make it non-positive and thus return -1.
• In any other case, return the reply.

Beneath is the implementation of the above strategy.

## C++

 ` `  `#embody ` `utilizing` `namespace` `std;` ` `  `int` `minimumOperations(``int` `N, ``int` `X,` `                      ``vector<``int``> nums)` `{` ` `  `    ` `    ``int` `ans = 0;` ` `  `    ` `    ` `    ``priority_queue<``int``> pq;` ` `  `    ` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``pq.push(nums[i]);` ` `  `    ` `    ` `    ` `    ``whereas` `(!pq.empty() and X > 0) {` `        ``if` `(pq.high() == 0)` `            ``break``;` ` `  `        ` `        ``ans++;` ` `  `        ` `        ``int` `num = pq.high();` ` `  `        ` `        ``pq.pop();` ` `  `        ` `        ` `        ``X -= num;` `        ``num /= 2;` ` `  `        ` `        ` `        ` `        ``if` `(num > 0)` `            ``pq.push(num);` `    ``}` ` `  `    ` `    ` `    ` `    ``if` `(X > 0)` `        ``return` `-1;` ` `  `    ` `    ` `    ``return` `ans;` `}` ` `  `int` `foremost()` `{` `    ``int` `N = 3;` `    ``vector<``int``> nums = { 3, 4, 12 };` `    ``int` `X = 25;` ` `  `    ` `    ``cout << minimumOperations(N, X, nums);` `    ``return` `0;` `}`

Time Complexity: O(N * log N)
Auxiliary House: O(N)

RELATED ARTICLES