Minimum Fuel Cost to Report to the Capital

Medium
935.

Minimum Fuel Cost to Report to the Capital

Minimum Fuel Cost to Report to the Capital is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Uber interviews.

A country has n cities numbered 0 … n - 1 joined by n - 1 bidirectional roads, forming a tree. City 0 is the capital, and every other city has one representative who must reach it.

Each representative starts with a car that seats seats people. A car burns one litre of fuel per road it drives, and representatives who meet in a city may share a car — as long as no car carries more than seats people. Return the minimum litres needed for everyone to reach the capital.

Example 1

Input
roads = [[0,1],[0,2],[0,3]], seats = 5
Output
3
Explanation
Three representatives each drive one road.

Example 2

Input
roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output
7

Example 3

Input
roads = [], seats = 1
Output
0
Explanation
Only the capital exists.

Constraints

  • 1 <= n <= 1000
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= roads[i][0], roads[i][1] < n
  • roads represents a valid tree
  • 1 <= seats <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} roads
 * @param {number} seats
 * @return {number}
 */
var minimumFuelCost = function(roads, seats) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Fuel Cost to Report to the Capital — Solution

Minimum Fuel Cost to Report to the Capital solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Fuel Cost to Report to the Capital is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Uber interviews.

Problem statement

A country has n cities numbered 0 … n - 1 joined by n - 1 bidirectional roads, forming a tree. City 0 is the capital, and every other city has one representative who must reach it.

Each representative starts with a car that seats seats people. A car burns one litre of fuel per road it drives, and representatives who meet in a city may share a car — as long as no car carries more than seats people. Return the minimum litres needed for everyone to reach the capital.

Example 1

Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation: Three representatives each drive one road.

Example 2

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output: 7

Example 3

Input: roads = [], seats = 1
Output: 0
Explanation: Only the capital exists.

Constraints

  • 1 <= n <= 1000
  • roads.length == n - 1
  • roads[i].length == 2
  • 0 <= roads[i][0], roads[i][1] < n
  • roads represents a valid tree
  • 1 <= seats <= 100

Hints for Minimum Fuel Cost to Report to the Capital

  1. Hint 1

    Every representative in a subtree must cross the single road joining that subtree to its parent.

  2. Hint 2

    So the cost of that road is decided only by how many people are behind it.

  3. Hint 3

    Carrying p people over one road needs ceil(p / seats) cars, hence that many litres.

How to solve Minimum Fuel Cost to Report to the Capital

Root the tree at the capital. The edge above a node is crossed by exactly the people in its subtree, and ferrying p people across one road costs ceil(p / seats) litres. Sum that over every edge.

Approach

  1. Build the tree and record a traversal order with each node's parent.
  2. Walk the order backwards so children are finished before their parent, accumulating subtree sizes.
  3. For each non-root node add ceil(size / seats) to the answer.

Why it works

The edges decouple completely because the graph is a tree: there is exactly one road out of each subtree, so its traffic is fixed at the subtree's population no matter how the cars are arranged. Once traffic is fixed, filling cars to capacity is optimal on every edge independently, which is why a greedy sum over edges is exact and no search is needed.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The root has no edge above it and contributes nothing.
  • Use (size + seats - 1) / seats rather than floating-point division.
  • An iterative traversal avoids a deep recursion on a path-shaped tree.

Reference solution

Python

from typing import List

def minimumFuelCost(roads: List[List[int]], seats: int) -> int:
    n = len(roads) + 1
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append(v)
        adj[v].append(u)
    parent = [-1] * n
    order = []
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if seen[v]:
                continue
            seen[v] = True
            parent[v] = u
            stack.append(v)
    cnt = [1] * n
    fuel = 0
    for i in range(len(order) - 1, 0, -1):
        u = order[i]
        cnt[parent[u]] += cnt[u]
        fuel += (cnt[u] + seats - 1) // seats
    return fuel

Java

public static int minimumFuelCost(int[][] roads, int seats) {
    int n = roads.length + 1;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] r : roads) {
        adj.get(r[0]).add(r[1]);
        adj.get(r[1]).add(r[0]);
    }
    int[] parent = new int[n];
    Arrays.fill(parent, -1);
    boolean[] seen = new boolean[n];
    int[] order = new int[n];
    int cntOrder = 0;
    int[] stack = new int[n];
    int top = 0;
    stack[top++] = 0;
    seen[0] = true;
    while (top > 0) {
        int u = stack[--top];
        order[cntOrder++] = u;
        for (int v : adj.get(u)) {
            if (seen[v]) continue;
            seen[v] = true;
            parent[v] = u;
            stack[top++] = v;
        }
    }
    int[] cnt = new int[n];
    Arrays.fill(cnt, 1);
    int fuel = 0;
    for (int i = cntOrder - 1; i >= 1; i--) {
        int u = order[i];
        cnt[parent[u]] += cnt[u];
        fuel += (cnt[u] + seats - 1) / seats;
    }
    return fuel;
}

C++

int minimumFuelCost(vector<vector<int>>& roads, int seats) {
    int n = (int) roads.size() + 1;
    vector<vector<int>> adj(n);
    for (auto& r : roads) {
        adj[r[0]].push_back(r[1]);
        adj[r[1]].push_back(r[0]);
    }
    vector<int> parent(n, -1), order;
    vector<char> seen(n, 0);
    vector<int> stack = { 0 };
    seen[0] = 1;
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        order.push_back(u);
        for (int v : adj[u]) {
            if (seen[v]) continue;
            seen[v] = 1;
            parent[v] = u;
            stack.push_back(v);
        }
    }
    vector<int> cnt(n, 1);
    int fuel = 0;
    for (int i = (int) order.size() - 1; i >= 1; i--) {
        int u = order[i];
        cnt[parent[u]] += cnt[u];
        fuel += (cnt[u] + seats - 1) / seats;
    }
    return fuel;
}

JavaScript

var minimumFuelCost = function(roads, seats) {
    var n = roads.length + 1, i;
    var adj = [];
    for (i = 0; i < n; i++) adj.push([]);
    for (i = 0; i < roads.length; i++) {
        adj[roads[i][0]].push(roads[i][1]);
        adj[roads[i][1]].push(roads[i][0]);
    }
    var parent = [], seen = [];
    for (i = 0; i < n; i++) { parent.push(-1); seen.push(false); }
    var order = [];
    var stack = [0];
    seen[0] = true;
    while (stack.length > 0) {
        var u = stack.pop();
        order.push(u);
        for (i = 0; i < adj[u].length; i++) {
            var v = adj[u][i];
            if (seen[v]) continue;
            seen[v] = true;
            parent[v] = u;
            stack.push(v);
        }
    }
    var cnt = [];
    for (i = 0; i < n; i++) cnt.push(1);
    var fuel = 0;
    for (i = order.length - 1; i >= 1; i--) {
        var w = order[i];
        cnt[parent[w]] += cnt[w];
        fuel += Math.floor((cnt[w] + seats - 1) / seats);
    }
    return fuel;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)