CodingGyan

Gas Station Circuit

hard Logic and Interview Sets

Problem

There are n gas stations on a circle. At station i you get gas[i] fuel and the trip to the next station costs cost[i] fuel. The tank is empty at the start and has no size limit. Print the smallest index of a station where you can start and drive around the full circle, or -1 if this is not possible. The first array is gas, the second array is cost.

Constraints

  • 1 <= n <= 10^5

Examples

Input

5
1 2 3 4 5
5
3 4 5 1 2

Output

3

Solutions

Best approachTime O(n)Space O(1)

Trying every start is O(n^2). One pass is enough: when the tank gets negative at station i, every start between the old start and i fails too, so we move the start to i + 1. The smallest valid start is returned because a valid start is unique when the total is not negative and we always take the first candidate that survives to the end.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find the start.
 * Input   : Two arrays: gas and cost.
 * Output  : A start index or -1.
 * Approach: Greedy.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a, int[] b) {
        // Step 1: If all the fuel together is less than all the costs, no start works.
        int total = 0;
        int tank = 0;
        int start = 0;
        for (int i = 0; i < a.length; i++) {
            int gain = a[i] - b[i];
            total += gain;
            tank += gain;
            // Step 2: If the tank gets negative, no station from start to i can be the start. Try the next one.
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        // Step 3: When the total is not negative, the last candidate start works.
        return total >= 0 ? start : -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int sizeB = scanner.nextInt();
        int[] b = new int[sizeB];
        for (int i = 0; i < sizeB; i++) {
            b[i] = scanner.nextInt();
        }
        System.out.println(solve(a, b));
    }
}
Hints (1)
  1. Why can we skip all starts before i after a failure?

Try these next