Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U. S. dollar buys 49 Indian rupees, 1 Indian rupee buys 2 Japanese yen, and 1 Japanese yen buys 0:0107 U. S. dollars. Then, by converting currencies, a trader can start with 1 U. S. dollar and buy 49 2 0:0107 D 1:0486 U. S. dollars, thus turning a profit of 4:86 percent. Suppose that we are given n currencies c1,c2,…, cn and an n × n table R of exchange rates, such that one unit of currency ci buys R[i, j] units of currency cj. Required:
Give an efficient algorithm to print out such a sequence if one exists. Analyze the running time of your algorithm.