Unit conversion ii

Array Math Depth-First Search Breadth-First Search Graph Theory

68.3% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn query_conversions(conversions: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    const MOD: i64 = 1_000_000_007;
    
    fn power(mut base: i64, mut exp: i64, modulus: i64) -> i64 {
      let mut result = 1i64;
      base %= modulus;
      while exp > 0 {
        if exp & 1 == 1 {
          result = result * base % modulus;
        }
        exp >>= 1;
        base = base * base % modulus;
      }
      result
    }
    
    fn mod_inv(a: i64, modulus: i64) -> i64 {
      power(a, modulus - 2, modulus)
    }
    
    // Build tree from conversions. It's a tree with n nodes.
    let n = conversions.len() + 1;
    let mut adj = vec![vec![]; n];
    for c in &conversions {
      let s = c[0] as usize;
      let t = c[1] as usize;
      let f = c[2] as i64;
      adj[s].push((t, f));
      adj[t].push((s, f));
    }
    
    // Root at 0. For each node, compute conversion factor from 0 to node.
    // factor[node] = number of units of type `node` equivalent to 1 unit of type 0.
    // If 0 -> 1 with factor 2, then factor[1] = 2.
    // For query (a, b): answer = factor[b] * mod_inv(factor[a])
    let mut factor = vec![1i64; n];
    let mut visited = vec![false; n];
    let mut stack = vec![0usize];
    visited[0] = true;
    
    while let Some(u) = stack.pop() {
      for &(v, f) in &adj[u] {
        if !visited[v] {
          visited[v] = true;
          // If edge is source->target with factor f:
          // 1 unit of source = f units of target
          // factor[target] = factor[source] * f if going from source to target
          // But the tree edge could be either direction.
          // From conversions: source->target means 1 source = f target.
          // If u is the source side: factor[v] = factor[u] * f
          // If u is the target side: factor[v] = factor[u] * inv(f)
          // We stored both directions in adj. Need to know the original direction.
          // In adj[s], we stored (t, f) and in adj[t], we stored (s, f).
          // Going from u to v: if (u,v,f) is original, then factor[v] = factor[u] * f
          // If (v,u,f) is original, then 1 unit v = f units u, 
          // so 1 unit u = 1/f units v, so factor[v] = factor[u] / f
          // But we stored the same f in both directions! Need to distinguish.
          // Let me re-store with direction info.
          // Actually let's store (neighbor, multiplier_from_u_to_neighbor)
          // Going from adj, I'll rebuild.
          // For now, let me just fix the adj construction.
          // This approach won't work cleanly. Let me rebuild.
          // I stored (t, f) for both sides, but the meaning differs.
          // Let me use signed: from source, factor is f; from target, factor is inv(f).
          factor[v] = factor[u] * f % MOD; // placeholder, will fix
          stack.push(v);
        }
      }
    }
    
    // Need to rebuild with proper direction. Let me redo.
    let mut adj2: Vec<Vec<(usize, i64)>> = vec![vec![]; n];
    for c in &conversions {
      let s = c[0] as usize;
      let t = c[1] as usize;
      let f = c[2] as i64;
      // s->t: 1 unit s = f units t. Going from s to t, multiply by f.
      adj2[s].push((t, f));
      // Going from t to s, multiply by inv(f).
      adj2[t].push((s, mod_inv(f, MOD)));
    }
    
    let mut factor = vec![1i64; n];
    let mut visited = vec![false; n];
    let mut stack = vec![0usize];
    visited[0] = true;
    
    while let Some(u) = stack.pop() {
      for &(v, mult) in &adj2[u] {
        if !visited[v] {
          visited[v] = true;
          factor[v] = factor[u] * mult % MOD;
          stack.push(v);
        }
      }
    }
    
    // For query (a, b): how many units of b = 1 unit of a?
    // factor[a] = units of a per 1 unit of 0
    // factor[b] = units of b per 1 unit of 0
    // So 1 unit of a = (1/factor[a]) units of 0 = (factor[b]/factor[a]) units of b
    queries.iter().map(|q| {
      let a = q[0] as usize;
      let b = q[1] as usize;
      (factor[b] % MOD * mod_inv(factor[a], MOD) % MOD) as i32
    }).collect()
  }
}