Description
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 0.7 British pound, 1 British pound buys 9.5 French francs, and 1 French franc buys 0.16 U.S. dollar.
Then by converting currencies, a trader can start with 1 U.S. dollar and buy 0.7 × 9.5 × 0.16 = 1.064 U.S. dollars, thus turning a profit of 6.4 percent. Suppose that we are given n currencies. Give an efficient algorithm to determine whether or not there exists a sequence of currencies.
