Minimum Fuel Cost to Report to the Capital
Asked at Uber
Problem
There are n cities numbered 0 to n-1 with the capital at city 0. Representatives from each city need to travel to the capital using roads. Each car holds seats people. Each road has a cost of 1 liter of fuel per person. Find the minimum total fuel needed. This is a tree DFS problem where you compute subtree sizes to minimize fuel consumption.
Asked At
| Company | Difficulty | |
|---|---|---|
| Uber | Medium | View all Uber questions → |
How to Think About It
Think of the cities as a tree rooted at the capital (city 0). Each representative must travel from their city to city 0. The fuel cost for a road is the number of people passing through it.
Key insight: for each road, the number of people passing through it equals the size of the subtree rooted at the child node (all representatives in that subtree must cross that road to reach the capital).
Use DFS to compute subtree sizes. For each node, count the number of representatives in its subtree. The fuel cost for the edge from this node to its parent is ceil(subtree_size / seats).
Visual walkthrough for roads = [[0,1],[0,2],[0,3]], seats = 2:
Tree: 0 is root, children: 1, 2, 3.
Subtree sizes: node 1 = 1, node 2 = 1, node 3 = 1.
Edge 1->0: ceil(1/2) = 1 car, fuel = 1.
Edge 2->0: ceil(1/2) = 1 car, fuel = 1.
Edge 3->0: ceil(1/2) = 1 car, fuel = 1.
Total fuel = 3.
For roads = [[0,1],[0,2],[1,3],[1,4]], seats = 2:
Tree: 0->{1,2}, 1->{3,4}.
Subtree: node 3=1, node 4=1, node 1=1+1+1=3 (itself + 3 + 4), node 2=1, node 0=1+3+1=5.
Edge 3->1: ceil(1/2)=1. Edge 4->1: ceil(1/2)=1. Edge 1->0: ceil(3/2)=2. Edge 2->0: ceil(1/2)=1.
Total fuel = 1+1+2+1 = 5.
Edge cases: single city (no roads, fuel=0), all representatives in one city (only one subtree needs cars), seats=1 (each person needs a car, fuel = n-1).
Optimal Approach
Step 1: Build the tree as an adjacency list.
Step 2: DFS from the capital (city 0). For each node:
- Count the number of representatives in its subtree (including itself)
- For each child edge, the fuel cost is ceil(child_subtree_size / seats)
`- Return the total subtree size to the parent
Step 3: Sum all edge costs to get total fuel.
DFS computes subtree sizes bottom-up. Each edge cost is deterministic: it's the number of cars needed to transport all representatives in that subtree.
Time: O(n) -- each node and edge visited once. Space: O(n) for the adjacency list and recursion stack.
What Trips People Up in Real Interviews
Not using ceil division. If 3 people need a car with 2 seats, you need 2 cars, not 1. Use (people + seats - 1) // seats or math.ceil(people / seats).
Forgetting that the capital (city 0) doesn't need to pay fuel. Its representatives are already at the destination. Only edges leading TO the capital contribute fuel.
Using BFS instead of DFS. BFS works but DFS is more natural for computing subtree sizes. DFS returns the count bottom-up, which directly gives you the number of people on each edge.
Not building the tree as an undirected graph. The roads are bidirectional, so add edges in both directions. When DFS, skip the parent to avoid revisiting.
Computing fuel as subtree_size // seats instead of ceil(subtree_size / seats). Integer division truncates. You need ceiling division to account for partially filled cars.
Solution Code
from collections import defaultdict
import math
def minimumFuelCost(roads, seats):
graph = defaultdict(list)
for a, b in roads:
graph[a].append(b)
graph[b].append(a)
total_fuel = [0]
def dfs(node, parent):
people = 1
for neighbor in graph[node]:
if neighbor != parent:
people += dfs(neighbor, node)
if node != 0:
total_fuel[0] += math.ceil(people / seats)
return people
dfs(0, -1)
return total_fuel[0]Frequently Asked Questions
What is the Minimum Fuel Cost to Report to the Capital problem?
There are n cities numbered 0 to n-1 with the capital at city 0. Representatives from each city need to travel to the capital using roads. Each car holds `seats` people. Each road has a cost of 1 liter of fuel per person. Find the minimum total fuel needed. This is a tree DFS problem where you compute subtree sizes to minimize fuel consumption.
How do you solve Minimum Fuel Cost to Report to the Capital?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Minimum Fuel Cost to Report to the Capital?
Minimum Fuel Cost to Report to the Capital is asked at Uber. It is a medium difficulty problem.
What are common mistakes on Minimum Fuel Cost to Report to the Capital?
- Not using ceil division. If 3 people need a car with 2 seats, you need 2 cars, not 1. Use `(people + seats - 1) // seats` or `math.ceil(people / seats)`.
- Forgetting that the capital (city 0) doesn't need to pay fuel. Its representatives are already at the destination. Only edges leading TO the capital contribute fuel.
- Using BFS instead of DFS. BFS works but DFS is more natural for computing subtree sizes. DFS returns the count bottom-up, which directly gives you the number of people on each edge.
- Not building the tree as an undirected graph. The roads are bidirectional, so add edges in both directions. When DFS, skip the parent to avoid revisiting.
- Computing fuel as `subtree_size // seats` instead of `ceil(subtree_size / seats)`. Integer division truncates. You need ceiling division to account for partially filled cars.