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 through which they’re purchased.

Examples:

Enter: arr[] = [ [ 7, 2 ], [ 10, 5 ], [ 2, 1] ] 
Output: 16
Clarification: 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 aspect (15-7+2) = 10.
After shopping for the second aspect (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 instances
[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 Strategy: To resolve the issue comply with the beneath concept:

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

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

Environment friendly Strategy: This downside might be solved through the use of the beneath statement:

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

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

• Iterate by way of 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)