1091. Currency Loop
A money-changer lists exchange rates between n currencies. The entry rates[i][j] says that one unit of currency i can be swapped for rates[i][j] units of currency j. You may chain any number of swaps, and a swap from a currency to itself is also allowed.
A loop is a chain of at least one swap that starts and ends in the same currency. Its gain is the product of the rates along the chain. Return true if some loop has a gain strictly greater than 1, meaning you can end with more of a currency than you started with, and false otherwise.
Rates are given with at most six decimal places. The tests guarantee that the best loop never has a gain strictly between 1 and 1.00001, so floating-point rounding cannot change the answer.
Example 1
- Input:
- rates = [[1,0.5,0.2],[2,1,0.4],[5,2.5,1]]
- Output:
- false
- Explanation:
These rates all come from fixed prices (1, 2 and 5), so every loop returns exactly the amount you started with and nothing is gained.
Example 2
- Input:
- rates = [[1,0.5,0.1],[2,1,0.25],[10,4,1]]
- Output:
- true
- Explanation:
Going 0 -> 1 -> 2 -> 0 multiplies by 0.5 * 0.25 * 10 = 1.25, so one unit grows to 1.25 units.
Example 3
- Input:
- rates = [[1,2,4],[0.45,1,2],[0.2,0.45,1]]
- Output:
- false
- Explanation:
Several single rates are above 1, but every way back loses money (for example 2 * 0.45 = 0.9), so no loop is profitable.
Constraints
1 ≤ n ≤ 100, rates is an n x n matrix
0.001 ≤ rates[i][j] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n^3)
- Space
- O(n^2)