Minimize Transaction Fees Path
PhonePe processes millions of transactions daily across various payment gateways. Optimizing the transaction routing to minimize costs is crucial for both PhonePe and its users. This problem challenges you to find the most cost-effective path between two payment gateways in a network, considering percentage-based transaction fees.
Implement a function minTransactionFeePath that determines the minimum total effective transaction fee to transfer funds from a startGateway to an endGateway within a given network of payment gateways and transaction routes.
The total effective fee for a path is calculated as follows: If a path consists of transactions with individual percentage fees f1, f2, ..., fk, the total effective fee is ((1 + f1/100) * (1 + f2/100) * ... * (1 + fk/100) - 1) * 100. Your goal is to minimize the (1 + f1/100) * ... * (1 + fk/100) product and then convert it back to a percentage.
If no path exists between the startGateway and endGateway, return -1.0.
Function Signature:
function minTransactionFeePath(numGateways: number, transactions: number[][], startGateway: number, endGateway: number): number
Parameters:
numGateways: An integer representing the total number of payment gateways, indexed from 0 to numGateways - 1.transactions: A 2D array of integers, where each inner array [source, destination, feePercentage] represents a directed transaction route from source gateway to destination gateway with an associated feePercentage.startGateway: An integer representing the index of the starting payment gateway.endGateway: An integer representing the index of the ending payment gateway.Return Value:
number (float/double) representing the minimum total effective transaction fee percentage.-1.0 if no path exists from startGateway to endGateway.feePercentage values are non-negative.startGateway == endGateway, the minimum effective fee is 0.0, representing no transactions needed. This is true even if there are self-loops with fees.Examples
Example 1
Input:
numGateways = 3, transactions = [[0,1,10],[1,2,5]], startGateway = 0, endGateway = 2
Output:
15.5
Note:
Path 0 -> 1 -> 2: (1 + 10/100) * (1 + 5/100) = 1.1 * 1.05 = 1.155. Effective fee = (1.155 - 1) * 100 = 15.5.
Example 2
Input:
numGateways = 4, transactions = [[0,1,10],[0,2,20],[1,3,5],[2,3,2]], startGateway = 0, endGateway = 3
Output:
15.5
Note:
Path 0 -> 1 -> 3: (1 + 10/100) * (1 + 5/100) = 1.1 * 1.05 = 1.155 (15.5% fee). Path 0 -> 2 -> 3: (1 + 20/100) * (1 + 2/100) = 1.2 * 1.02 = 1.224 (22.4% fee). The minimum is 15.5.
Example 3
Input:
numGateways = 2, transactions = [[0,1,10]], startGateway = 1, endGateway = 0
Output:
-1.0
Note:
There is no path from gateway 1 to gateway 0.
Example 4
Input:
numGateways = 2, transactions = [[0,0,5],[0,1,10]], startGateway = 0, endGateway = 0
Output:
0.0
Note:
Since startGateway is equal to endGateway, the minimum effective fee is 0.0 (no transactions needed).
Constraints
1 <= numGateways <= 10000 <= transactions.length <= numGateways * (numGateways - 1)transactions[i] will always be of the form [source, destination, feePercentage]0 <= source, destination < numGateways0 <= feePercentage <= 1000 <= startGateway, endGateway < numGatewaysstartGateway == endGateway.Loading editor...