Minimal cash required to purchase objects with given cashbacks

Given an array arr[] of size N, denoting the price of N objects and the cashback upon shopping for that merchandise, the duty is to search out the minimal sum of money required to purchase all of the objects regardless of the order during which they’re purchased.

Examples:

Enter: arr[] = [ [ 7, 2 ], [ 10, 5 ], [ 2, 1] ] 
Output: 16
Rationalization: The geek should buy the goodies within the following methods:
[7, 2] ->  [10, 5] -> [2, 1]  minimal cash required are 15.
Initially 15. After shopping for the primary ingredient (15-7+2) = 10.
After shopping for the second ingredient (10-10+5) = 5.
After buyin the third merchandise (5-2+1) = 4.
If something lower than 15 was used then one wouldn’t manage to pay for
to purchase the second merchandise. Similary for the next circumstances
[7, 2] -> [2, 1] -> [10, 5] minimal cash required is 16
[10, 5] -> [7, 2] -> [2, 1] minimal cash required is12
[10, 5] -> [2, 1] -> [7, 2] minimal cash required is 13
[2, 1] -> [7, 2] -> [10, 5] minimal cash required is 16
[2, 1] -> [10, 5] -> [7, 2] minimal cash required is 13
Within the worst case, geek requires 16 unit of cash

Enter: arr[] = [ [ 5, 6 ], [40, 2], [89, 8] ]
Output: 127

Naive Method: To unravel the issue observe the beneath concept:

Generate all of the methods attainable and discover the minimal cash required for every permutaion.

Time Complexity: O(N*N!)
Auxiliary Area: O(N)

Environment friendly Method: This drawback might be solved by utilizing the beneath remark:

• Calculate the efficient sum of money spent on objects the place the value ≥ refund. Efficient quantity spend = value – refund. 
• Calculate the utmost value amongst these objects the place the refund > value. Efficient quantity spend = value of most costly merchandise.
• Add refund from the final transaction as a result of we can’t use refund from the final transaction to scale back efficient quantity spend. 
  • Final transaction in worst case will probably be both having most refund such that value of that merchandise > refund. 
  • In any other case, final transaction could have most value if refund on buying that merchandise is bigger than its value.

Observe the steps talked about beneath to implement the above concept:

• Iterate by the array from i = 0 to N-1:
  • Add the efficient value.
  • In every iteration calculate the utmost worth incurred within the final transaction in worst case utilizing the ide talked about above.
• On the finish add the utmost value of final transaction in worst case with the full efficient value to get the required reply.

Beneath is the implementation of the above concept.

Time Complexity: O(N)
Auxiliary Area: O(1)