Medium

Unit Conversion II

LAB

Given bidirectional conversions [a,b,factor] meaning a = factor*b, return the product to convert source into target, rounded to 6 decimals as an integer scaled by 1e6.

EXAMPLES

Example 1

Input
{
  "conversions": [
    [
      0,
      1,
      2
    ],
    [
      1,
      2,
      5
    ]
  ],
  "source": 0,
  "target": 2
}

Output
10000000

FUNCTION SHAPE

conversions: intMatrixsource: inttarget: int→int

SOLUTION NOTE

Convert A→B = dp(B) / dp(A) using modular inverse. dp(i) is rate from unit 0 to i.

Reveal reference solution +

pythonREFERENCE

def queryConversions(self, conversions: List[List[int]], queries: List[List[int]]) -> List[int]:
    n = len(conversions)
    MOD = 10**9 + 7
    parent = {}
    for u, v, w in conversions:
        parent[v] = (u, w)

    @cache
    def dp(i):
        if i == 0: return 1
        par, w = parent[i]
        return (w * dp(par)) % MOD

    return [(pow(dp(a), -1, MOD) * dp(b)) % MOD for a, b in queries]

TimeO(n + q)

SpaceO(n)

Open on LeetCode ↗