Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Greedy

Gas Station

Medium · Greedy · Asked at Amazon, Google, Microsoft, Bloomberg

Gas stations stand in a circle. Station i gives gas[i] fuel and driving to the next station costs cost[i]. With an empty tank, from which station can you start to travel around the circuit once? Print the smallest such index (0-based), or -1 if impossible. (When a solution exists it is unique.)

Input

First line: n. Second line: gas. Third line: cost.

Output

The starting index, or -1.

Constraints

If total gas < total cost it is impossible. Otherwise scan once: whenever the running tank drops below 0, no station so far can be the start — restart from the next one.

Example 1

Input

5
1 2 3 4 5
3 4 5 1 2

Output

3

Example 2

Input

3
2 3 4
3 4 3

Output

-1

Hints

  1. If the total gas is less than the total cost, no start works.
  2. Otherwise scan once with a running tank. If it becomes negative at station i, none of the stations from the current start to i can be the start — try i + 1 next.

Approach

Keep total (sum of gas − cost) and tank (since the current candidate start). When tank < 0 after station i, any start between the candidate and i would arrive at i with even less fuel, so reset start = i + 1, tank = 0. At the end, if total ≥ 0 the candidate start completes the circuit (a classic argument shows the remaining deficit is covered), otherwise print −1. The valid start, when it exists, is unique.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> gas(n), cost(n);
    for (auto &x : gas) cin >> x;
    for (auto &x : cost) cin >> x;
    long long total = 0, tank = 0;
    int start = 0;
    for (int i = 0; i < n; i++) {
        total += gas[i] - cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) start = i + 1, tank = 0;
    }
    cout << (total < 0 ? -1 : start) << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
gas, cost = data[1 : 1 + n], data[1 + n : 1 + 2 * n]
total = tank = start = 0
for i in range(n):
    total += gas[i] - cost[i]
    tank += gas[i] - cost[i]
    if tank < 0:
        start, tank = i + 1, 0
print(-1 if total < 0 else start)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] gas = new long[n], cost = new long[n];
        for (int i = 0; i < n; i++) gas[i] = sc.nextLong();
        for (int i = 0; i < n; i++) cost[i] = sc.nextLong();
        long total = 0, tank = 0;
        int start = 0;
        for (int i = 0; i < n; i++) {
            total += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) { start = i + 1; tank = 0; }
        }
        System.out.println(total < 0 ? -1 : start);
    }
}

Solve Gas Station online · All practice problems