Skip to content

3528. Unit Conversion I

SourceBiweekly Contest 155 Q2DifficultyMediumRating1579

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

Thinking

There are \(n-1\) conversions and a unique path from \(0\), so the graph is a tree rooted at \(0\). We need how many units of \(i\) equal one unit of \(0\).

Store multipliers in an adjacency list and DFS from the root, multiplying modulo \(10^9+7\) into \(\textit{ans}[i]\).

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 time 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;
}

Solution 2: Explicit Stack

Thinking

There are \(n - 1\) conversions and a unique path from \(0\), so the graph is a tree rooted at \(0\). We need how many units of \(i\) equal one unit of \(0\), modulo \(10^9 + 7\).

With \(n \le 10^5\), recursing from the root into the next unit reaches depth \(n\) on a chain and overflows the call stack. Each unit's factor depends only on the unique path from the root, so sibling order does not matter.

An explicit stack of \((\textit{unit}, \textit{accumulated}\ \textit{factor})\) therefore starts at \((0, 1)\). Popping a frame writes the factor into the answer, and each successor is pushed with the current factor multiplied by the edge weight, modulo \(10^9 + 7\).

The problem guarantees that unit 0 can be converted to any other unit through a unique conversion path, and the length of \(\textit{conversions}\) is \(n - 1\), so the conversions form a directed tree rooted at \(0\).

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.

An explicit stack then walks from the root. Each frame is \((\textit{unit}, \textit{accumulated}\ \textit{factor})\), starting from \((0, 1)\). Popping a frame writes the factor into the answer. For each successor \(t\) with edge weight \(w\), we push \((t, \textit{mul} \times w \bmod (10^9 + 7))\).

Finally, we return the answer array.

The time 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]:
        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
        stk = [(0, 1)]
        while stk:
            s, mul = stk.pop()
            ans[s] = mul
            for t, w in g[s]:
                stk.append((t, mul * w % mod))
        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
class Solution {
    public int[] baseUnitConversions(int[][] conversions) {
        final int mod = (int) 1e9 + 7;
        int n = conversions.length + 1;
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : conversions) {
            g[e[0]].add(new int[] {e[1], e[2]});
        }
        int[] ans = new int[n];
        Deque<long[]> stk = new ArrayDeque<>();
        stk.push(new long[] {0, 1});
        while (!stk.isEmpty()) {
            long[] cur = stk.pop();
            int s = (int) cur[0];
            long mul = cur[1];
            ans[s] = (int) mul;
            for (var e : g[s]) {
                stk.push(new long[] {e[0], mul * e[1] % mod});
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]});
        }
        vector<pair<int, long long>> stk{{0, 1}};
        while (!stk.empty()) {
            auto [s, mul] = stk.back();
            stk.pop_back();
            ans[s] = mul;
            for (auto [t, w] : g[s]) {
                stk.push_back({t, mul * w % mod});
            }
        }
        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)
    stk := [][2]int{{0, 1}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        s, mul := cur[0], cur[1]
        ans[s] = mul
        for _, e := range g[s] {
            stk = append(stk, [2]int{e.t, mul * e.w % mod})
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 stk: [number, number][] = [[0, 1]];
    while (stk.length) {
        const [s, mul] = stk.pop()!;
        ans[s] = mul;
        for (const { t, w } of g[s]) {
            stk.push([t, Number((BigInt(mul) * BigInt(w)) % mod)]);
        }
    }
    return ans;
}

Comments