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++
|
|
Time Complexity: O(N * log N)
Auxiliary House: O(N)
