You are given two integer arrays prices and discounts.
The value prices[i] represents the price of the ith item, and discounts[j] represents a discount percentage.
You may apply discounts subject to the following rules:
If a discount of d percent is applied to an item with price p, its final price becomes (p * (100 - d)) / 100. The final price is not rounded.
Return the minimum possible sum of final prices after assigning discounts optimally. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input: prices = [10,30,21], discounts = [50,60]
Output: 32.50000
Explanation:
discounts[1] = 60 to prices[1] = 30, thus 30 * (100 - 60) / 100 = 12.discounts[0] = 50 to prices[2] = 21, thus 21 * (100 - 50) / 100 = 10.5.prices[0] = 10 receives no discount, so it stays 10.The total is 12 + 10.5 + 10 = 32.50000, which is the minimum possible.
Example 2:
Input: prices = [100,70], discounts = [10,40,50]
Output: 92.00000
Explanation:
discounts[2] = 50 to prices[0] = 100, thus 100 * (100 - 50) / 100 = 50.discounts[1] = 40 to prices[1] = 70, thus 70 * (100 - 40) / 100 = 42.The total is 50 + 42 = 92.00000, which is the minimum possible.
Example 3:
Input: prices = [7,3,9], discounts = [100,100]
Output: 3.00000
Explanation:
discounts[0] = 100 to prices[2] = 9, thus 9 * (100 - 100) / 100 = 0.discounts[1] = 100 to prices[0] = 7, thus 7 * (100 - 100) / 100 = 0.prices[1] = 3 receives no discount, so it stays 3.The total is 0 + 0 + 3 = 3.00000, which is the minimum possible.
Constraints:
1 <= prices.length, discounts.length <= 1051 <= prices[i] <= 1051 <= discounts[j] <= 100To minimize the total price, we need to maximize the total amount saved by discounts. Applying a discount d to an item with price p saves p times d / 100. By the rearrangement inequality, applying larger discounts to more expensive items maximizes the total savings.
Therefore, we sort both prices and discounts in ascending order, then use two pointers starting from the ends of both arrays, repeatedly applying the current largest discount to the current most expensive item and accumulating the discounted price. Once all discounts are used up, the remaining items are added at their original prices.
The time complexity is O(n times log n + m times log m), and the space complexity is O(log n + log m). Here, n and m are the lengths of the arrays prices and discounts, respectively.
Python
Java
C++
Go
TypeScript
4014. Minimum Total Price After Applying Discounts (Leetcode Medium) • Programming Live with Larry • 68 views views
Watch 8 more video solutions →Practice Minimum Total Price After Applying Discounts with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor