Skip to content

3528. Unit Conversion I

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.

Return an array baseUnitConversion of length n, where baseUnitConversion[i] is the number of units of type i equivalent to a single unit of type 0. Since the answer may be large, return each baseUnitConversion[i] modulo 109 + 7.

 

Example 1:

Input: conversions = [[0,1,2],[1,2,3]]

Output: [1,2,6]

Explanation:

  • Convert a single unit of type 0 into 2 units of type 1 using conversions[0].
  • Convert a single unit of type 0 into 6 units of type 2 using conversions[0], then conversions[1].

Example 2:

Input: conversions = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]

Output: [1,2,3,8,10,6,30,24]

Explanation:

  • Convert a single unit of type 0 into 2 units of type 1 using conversions[0].
  • Convert a single unit of type 0 into 3 units of type 2 using conversions[1].
  • Convert a single unit of type 0 into 8 units of type 3 using conversions[0], then conversions[2].
  • Convert a single unit of type 0 into 10 units of type 4 using conversions[0], then conversions[3].
  • Convert a single unit of type 0 into 6 units of type 5 using conversions[1], then conversions[4].
  • Convert a single unit of type 0 into 30 units of type 6 using conversions[0], conversions[3], then conversions[5].
  • Convert a single unit of type 0 into 24 units of type 7 using conversions[1], conversions[4], then conversions[6].

 

Constraints:

  • 2 <= n <= 105
  • conversions.length == n - 1
  • 0 <= sourceUniti, targetUniti < n
  • 1 <= conversionFactori <= 109
  • It is guaranteed that unit 0 can be converted into any other unit through a unique combination of conversions without using any conversions in the opposite direction.

Solutions

Solution 1: DFS

Since the problem guarantees that unit 0 can be converted to any other unit through a unique conversion path, we can use Depth-First Search (DFS) to traverse all unit conversion relationships. Additionally, since the length of the \(\textit{conversions}\) array is \(n - 1\), representing \(n - 1\) conversion relationships, we can treat the unit conversion relationships as a tree, where the root node is unit 0, and the other nodes are the other units.

We can use an adjacency list \(g\) to represent the unit conversion relationships, where \(g[i]\) represents the units that unit \(i\) can convert to and the corresponding conversion factors.

Then, we start the DFS from the root node \(0\), i.e., call the function \(\textit{dfs}(s, \textit{mul})\), where \(s\) represents the current unit, and \(\textit{mul}\) represents the conversion factor from unit \(0\) to unit \(s\). Initially, \(s = 0\), \(\textit{mul} = 1\). In each recursion, we store the conversion factor \(\textit{mul}\) of the current unit \(s\) into the answer array, then traverse all adjacent units \(t\) of the current unit \(s\), and recursively call \(\textit{dfs}(t, \textit{mul} \times w \mod (10^9 + 7))\), where \(w\) is the conversion factor from unit \(s\) to unit \(t\).

Finally, we return the answer array.

The complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of units.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def baseUnitConversions(self, conversions: List[List[int]]) -> List[int]:
        def dfs(s: int, mul: int) -> None:
            ans[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))
        ans = [0] * n
        dfs(0, 1)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private final int mod = (int) 1e9 + 7;
    private List<int[]>[] g;
    private int[] ans;
    private int n;

    public int[] baseUnitConversions(int[][] conversions) {
        n = conversions.length + 1;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        ans = new int[n];
        for (var e : conversions) {
            g[e[0]].add(new int[] {e[1], e[2]});
        }
        dfs(0, 1);
        return ans;
    }

    private void dfs(int s, long mul) {
        ans[s] = (int) mul;
        for (var e : g[s]) {
            dfs(e[0], mul * e[1] % mod);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> baseUnitConversions(vector<vector<int>>& conversions) {
        const int mod = 1e9 + 7;
        int n = conversions.size() + 1;
        vector<vector<pair<int, int>>> g(n);
        vector<int> ans(n);
        for (const auto& e : conversions) {
            g[e[0]].push_back({e[1], e[2]});
        }
        auto dfs = [&](this auto&& dfs, int s, long long mul) -> void {
            ans[s] = mul;
            for (auto [t, w] : g[s]) {
                dfs(t, mul * w % mod);
            }
        };
        dfs(0, 1);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func baseUnitConversions(conversions [][]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})
    }

    ans := make([]int, n)

    var dfs func(s int, mul int)
    dfs = func(s int, mul int) {
        ans[s] = mul
        for _, e := range g[s] {
            dfs(e.t, mul*e.w%mod)
        }
    }

    dfs(0, 1)
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function baseUnitConversions(conversions: 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 ans: number[] = Array(n).fill(0);
    const dfs = (s: number, mul: number) => {
        ans[s] = mul;
        for (const { t, w } of g[s]) {
            dfs(t, Number((BigInt(mul) * BigInt(w)) % mod));
        }
    };
    dfs(0, 1);
    return ans;
}

Comments