Welcome to Subscribe On Youtube
3535. Unit Conversion II 🔒
Description
There are n types of units indexed from 0 to n - 1.
You are given a 2D integer array conversions of length n - 1, where conversions[i] = [sourceUniti, targetUniti, conversionFactori]. This indicates that a single unit of type sourceUniti is equivalent to conversionFactori units of type targetUniti.
You are also given a 2D integer array queries of length q, where queries[i] = [unitAi, unitBi].
Return an array answer of length q where answer[i] is the number of units of type unitBi equivalent to 1 unit of type unitAi, and can be represented as p/q where p and q are coprime. Return each answer[i] as pq-1 modulo 109 + 7, where q-1 represents the multiplicative inverse of q modulo 109 + 7.
Example 1:
Input: conversions = [[0,1,2],[0,2,6]], queries = [[1,2],[1,0]]
Output: [3,500000004]
Explanation:
- In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of
conversions[0], thenconversions[1]. - In the second query, we can convert unit 1 into 1/2 units of type 0 using the inverse of
conversions[0]. We return 500000004 since it is the multiplicative inverse of 2.
Example 2:
Input: conversions = [[0,1,2],[0,2,6],[0,3,8],[2,4,2],[2,5,4],[3,6,3]], queries = [[1,2],[0,4],[6,5],[4,6],[6,1]]
Output: [3,12,1,2,83333334]
Explanation:
- In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of
conversions[0], thenconversions[1]. - In the second query, we can convert unit 0 into 12 units of type 4 using
conversions[1], thenconversions[3]. - In the third query, we can convert unit 6 into 1 unit of type 5 using the inverse of
conversions[5], the inverse ofconversions[2],conversions[1], thenconversions[4]. - In the fourth query, we can convert unit 4 into 2 units of type 6 using the inverse of
conversions[3], the inverse ofconversions[1],conversions[2], thenconversions[5]. - In the fifth query, we can convert unit 6 into 1/12 units of type 1 using the inverse of
conversions[5], the inverse ofconversions[2], thenconversions[0]. We return 83333334 since it is the multiplicative inverse of 12.
Constraints:
2 <= n <= 105conversions.length == n - 10 <= sourceUniti, targetUniti < n1 <= conversionFactori <= 1091 <= q <= 105queries.length == q0 <= unitAi, unitBi < n- It is guaranteed that unit 0 can be uniquely converted into any other unit through a combination of forward or backward conversions.
Solutions
Solution 1
-
class Solution { private final int mod = (int) 1e9 + 7; private List<int[]>[] g; private int[] res; public int[] queryConversions(int[][] conversions, int[][] queries) { int n = conversions.length + 1; g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (var e : conversions) { g[e[0]].add(new int[] {e[1], e[2]}); } res = new int[n]; dfs(0, 1); int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int x = queries[i][0], y = queries[i][1]; ans[i] = (int) ((long) res[y] * qpow(res[x], mod - 2) % mod); } return ans; } private void dfs(int s, long mul) { res[s] = (int) mul; for (var e : g[s]) { dfs(e[0], mul * e[1] % mod); } } private long qpow(long x, int n) { long res = 1; while (n > 0) { if ((n & 1) == 1) { res = res * x % mod; } x = x * x % mod; n >>= 1; } return res; } } -
class Solution { public: vector<int> queryConversions(vector<vector<int>>& conversions, vector<vector<int>>& queries) { const int mod = 1e9 + 7; int n = conversions.size() + 1; vector<vector<pair<int, int>>> g(n); for (auto& e : conversions) { g[e[0]].emplace_back(e[1], e[2]); } vector<int> res(n); auto dfs = [&](this auto&& dfs, int s, long long mul) -> void { res[s] = mul; for (auto [t, w] : g[s]) { dfs(t, mul * w % mod); } }; dfs(0, 1); auto qpow = [&](long long x, int n) { long long res = 1; while (n) { if (n & 1) { res = res * x % mod; } x = x * x % mod; n >>= 1; } return res; }; vector<int> ans; for (auto& q : queries) { ans.push_back(res[q[1]] * qpow(res[q[0]], mod - 2) % mod); } return ans; } }; -
class Solution: def queryConversions( self, conversions: List[List[int]], queries: List[List[int]] ) -> List[int]: def dfs(s: int, mul: int) -> None: res[s] = mul for t, w in g[s]: dfs(t, mul * w % mod) mod = 10**9 + 7 n = len(conversions) + 1 g = [[] for _ in range(n)] for s, t, w in conversions: g[s].append((t, w)) res = [0] * n dfs(0, 1) ans = [] for x, y in queries: ans.append(res[y] * pow(res[x], mod - 2, mod) % mod) return ans -
func queryConversions(conversions [][]int, queries [][]int) []int { const mod = int(1e9 + 7) n := len(conversions) + 1 g := make([][]struct{ t, w int }, n) for _, e := range conversions { s, t, w := e[0], e[1], e[2] g[s] = append(g[s], struct{ t, w int }{t, w}) } res := make([]int, n) var dfs func(int, int) dfs = func(s, mul int) { res[s] = mul for _, e := range g[s] { dfs(e.t, mul*e.w%mod) } } dfs(0, 1) qpow := func(x, n int) int { res := 1 for n > 0 { if n&1 > 0 { res = res * x % mod } x = x * x % mod n >>= 1 } return res } ans := make([]int, len(queries)) for i, q := range queries { ans[i] = res[q[1]] * qpow(res[q[0]], mod-2) % mod } return ans } -
function queryConversions(conversions: number[][], queries: number[][]): number[] { const mod = BigInt(1e9 + 7); const n = conversions.length + 1; const g: { t: number; w: number }[][] = Array.from({ length: n }, () => []); for (const [s, t, w] of conversions) { g[s].push({ t, w }); } const res: number[] = Array(n).fill(0); const dfs = (s: number, mul: number): void => { res[s] = mul; for (const { t, w } of g[s]) { dfs(t, Number((BigInt(mul) * BigInt(w)) % mod)); } }; dfs(0, 1); const qpow = (x: number, n: number): number => { let res = 1n; let a = BigInt(x); while (n > 0) { if (n & 1) { res = (res * a) % mod; } a = (a * a) % mod; n >>= 1; } return Number(res); }; const ans: number[] = []; for (const [x, y] of queries) { ans.push(Number((BigInt(res[y]) * BigInt(qpow(res[x], 1e9 + 5))) % mod)); } return ans; } -
impl Solution { pub fn query_conversions(conversions: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> { const MOD: i64 = 1_000_000_007; let n = conversions.len() + 1; let mut g = vec![Vec::<(usize, i64)>::new(); n]; for e in conversions { g[e[0] as usize].push((e[1] as usize, e[2] as i64)); } let mut res = vec![0_i64; n]; fn dfs(s: usize, mul: i64, g: &Vec<Vec<(usize, i64)>>, res: &mut Vec<i64>) { res[s] = mul; for &(t, w) in &g[s] { dfs(t, mul * w % MOD, g, res); } } dfs(0, 1, &g, &mut res); fn qpow(mut x: i64, mut n: i32) -> i64 { let mut res = 1_i64; while n > 0 { if n & 1 == 1 { res = res * x % MOD; } x = x * x % MOD; n >>= 1; } res } let mut ans = Vec::with_capacity(queries.len()); for q in queries { let x = q[0] as usize; let y = q[1] as usize; ans.push((res[y] * qpow(res[x], 1_000_000_005) % MOD) as i32); } ans } }