Optimal Payment Plan Selection
Razorpay processes millions of transactions daily for businesses across India. Optimizing the cost of these transactions is crucial for maintaining profitability and competitive pricing. Different payment processing plans offer varying fixed and percentage-based fees. Furthermore, switching between these plans can incur an administrative cost. As a key engineer, your task is to design an algorithm that determines the optimal sequence of plan selections to minimize the total fees incurred for a series of incoming payment requests.
You are given a sequence of payment amounts and a set of available plans, each with a fixedFee and a percentageFee. You also know a global switchCost that applies whenever you change from one plan to any other for consecutive payments. Your goal is to implement a function that calculates the minimum possible total fees incurred for processing all payments.
minTotalFees function.amounts, plans, and switchCost as input.number.amounts: An array of number representing the value of each payment request, in chronological order.plans: An array of objects, where each object represents a processing plan. Each plan object has two properties:
fixedFee: A number representing the fixed fee component of the plan.percentageFee: A number representing the percentage fee component (e.g., 2.5 for 2.5%).switchCost: A number representing the cost incurred when switching from any plan to any other different plan for consecutive payments.number representing the minimum total fees incurred across all payments.For a payment of amount using a plan with fixedFee and percentageFee:
Fee = fixedFee + (amount * percentageFee / 100.0)
amounts array will never be empty.number.switchCost is incurred. A switchCost is only applied when the chosen plan for payment i is different from the chosen plan for payment i-1. For the very first payment, no switchCost is ever applied.Examples
Example 1
Input:
amounts = [1000, 2000], plans = [{ "fixedFee": 10, "percentageFee": 1 }, { "fixedFee": 5, "percentageFee": 2 }], switchCost = 5
Output:
50
Note:
P0 for both payments: (10 + 10000.01) + (10 + 20000.01) = 20 + 30 = 50. This is the minimum.
Example 2
Input:
amounts = [500], plans = [{ "fixedFee": 0, "percentageFee": 3 }, { "fixedFee": 15, "percentageFee": 0 }], switchCost = 100
Output:
15
Note:
Only one payment. Using Plan 0: 0 + 5000.03 = 15. Using Plan 1: 15 + 5000 = 15. Both yield 15.
Example 3
Input:
amounts = [100, 100, 100], plans = [{ "fixedFee": 1, "percentageFee": 0 }, { "fixedFee": 0, "percentageFee": 1 }], switchCost = 0
Output:
3
Note:
With zero switch cost, for each payment of 100, Plan 0 (1 + 00.01 = 1) and Plan 1 (0 + 1000.01 = 1) both cost 1. Total = 1*3 = 3.
Constraints
1 <= amounts.length (N) <= 10^51 <= plans.length (K) <= 1001 <= amounts[i] <= 10^90 <= plans[j].fixedFee <= 10^60 <= plans[j].percentageFee <= 100 (integer percentage)0 <= switchCost <= 10^7Loading editor...