Minimum Fuel Cost to Report to the Capital

Problem

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0. You are given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Examples

Example 1:

graph TD;
	A(2) --- B(0)
	B --- C(1) & D(3)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input:
roads = [[0,1],[0,2],[0,3]], seats = 5
Output:
 3
Explanation: 
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative2 goes directly to the capital with 1 liter of fuel.
- Representative3 goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.

Example 2:

graph TD
    A(3)
    A --- B(1)
    A --- C(2)
    B --- D(0)
    D --- E(4)
    D --- F(5)
    E --- G(6)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input:
roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output:
 7
Explanation: 
- Representative2 goes directly to city 3 with 1 liter of fuel.
- Representative2 and representative3 go together to city 1 with 1 liter of fuel.
- Representative2 and representative3 go together to the capital with 1 liter of fuel.
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative5 goes directly to the capital with 1 liter of fuel.
- Representative6 goes directly to city 4 with 1 liter of fuel.
- Representative4 and representative6 go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.

Example 3:

graph TD;
	A(0)

1
2
3
4
5


Input:
roads = [], seats = 1
Output:
 0
Explanation: No representatives need to travel to the capital city.

Solution

Method 1 - DFS

The problem revolves around finding the minimum fuel cost to bring all representatives of the cities to the capital city, 0, through a bidirectional tree structure. Here are the steps:

Graph Representation:
- Represent the cities and roads as a graph using adjacency lists. This allows efficient traversal using DFS.
DFS to Aggregate Representatives:
- Traverse the graph starting from the capital city 0 using DFS.
- Count the number of representatives at each subtree. For any subtree with k representatives, the cars required are ceil(k / seats).
Calculate Fuel Costs:
- Accumulate the fuel cost by computing the cars required to gather representatives at each subtree and multiply the number of cars by the distance traveled (each edge costs 1 liter).
Optimal Travelling:
- Leverage the hierarchical tree structure which ensures that only one path is valid for each city to reach the capital, minimising cycles.

Code

 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
26
27
28
29
30
31
32
33
34


class Solution {
    public int minimumFuelCost(int[][] roads, int seats) {
        // Build adjacency list representation of the graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int n = roads.length + 1;
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] road : roads) {
            graph.get(road[0]).add(road[1]);
            graph.get(road[1]).add(road[0]);
        }

        long ans = 0;

        // DFS Function
        int dfs(int node, int parent) {
            int reps = 1; // Start with 1 representative (current city)
            for (int nei : graph.get(node)) {
                if (nei != parent) { // Avoid visiting parent
                    reps += dfs(nei, node);
                }
            }
            // Calculate cars needed for current subtree reps
            if (node != 0) { // Skip root city `0`, no fuel needed
                ans += Math.ceil((double) reps / seats); // Cost in terms of fuel
            }
            return reps; // Return total reps in subtree
        }

        dfs(0, -1); // Start DFS from capital city `0` with no parent
        return (int) ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        # Build adjacency list representation of the graph
        graph = {i: [] for i in range(len(roads) + 1)}
        for a, b in roads:
            graph[a].append(b)
            graph[b].append(a)
        
        ans = 0

        def dfs(node: int, parent: int) -> int:
            nonlocal ans
            reps = 1  # Start with 1 representative (current city)
            for nei in graph[node]:
                if nei != parent:  # Avoid visiting parent
                    reps += dfs(nei, node)
            # Calculate cars needed for current subtree reps
            if node != 0:  # Skip root city `0`, no fuel needed
                ans += ceil(reps / seats)  # Cost in terms of fuel
            return reps  # Return total reps in subtree
        
        dfs(0, -1)  # Start DFS from capital city `0` with no parent
        return ans

Complexity

⏰ Time complexity: O(n). Each node and edge is visited once during tree traversal.
🧺 Space complexity: O(n). To store the adjacency list and recursive function calls during DFS.

Problem#

Examples#

Solution#

Method 1 - DFS#

Code#

Complexity#