2477. Minimum Fuel Cost to Report to the Capital
Asked at Uber
Difficulty
Medium
Time
O(n)
Space
O(n)
Pattern
Tree
Companies
1
Problem
You are given a country made of n cities numbered 0 to n-1, connected by exactly n-1 bidirectional roads. Because there are no cycles, the cities form a tree. City 0 is the capital.
Every city sends one representative to a meeting in the capital. Each city has one car, and every car has the same number of seats, given by seats. A representative can drive their own car, or ride together with other representatives. Driving along one road always burns exactly 1 liter of fuel, no matter how many people are inside the car.
Return the minimum total liters of fuel needed to bring every representative to city 0. People may meet at intermediate cities, switch cars, and share rides to save fuel.
Everyone must reach city 0
Constraints
- ●
1 <= n <= 10^5 - ●
roads.length == n - 1 - ●
roads[i].length == 2 - ●
0 <= ai, bi < n - ●
ai != bi - ●
roads represents a valid tree - ●
1 <= seats <= 10^5
Examples
roads = [[0,1],[0,2],[0,3]], seats = 53roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 27roads = [], seats = 10Asked At
1 companies| 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).
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.
Count people in each subtree
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
O(n) timefrom 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
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.