package main

// It is toooo slow
func canCompleteCircuitOld(gas []int, cost []int) int {
	length := len(gas)
	for beg := 0; beg < length; beg++ {
		curr := (beg + 1) % length
		gasLeft := gas[beg] - cost[beg]
		for gasLeft >= 0 {
			if curr == beg {
				return curr
			}
			gasLeft += gas[curr] - cost[curr]
			curr = (curr + 1) % length
		}
	}
	return -1
}

// If car starts at A and can not reach B. Any station between A and B
// can not reach B. (B is the first station that A can not reach.)
// If the total number of gas is bigger than the total number of cost.
// There must be a solution.
func canCompleteCircuit(gas []int, cost []int) int {
	var total, sum, beg int
	for i := 0; i < len(gas); i++ {
		total += gas[i] - cost[i]
		sum += gas[i] - cost[i]
		if sum < 0 {
			beg = i + 1
			sum = 0
		}
	}
	if total < 0 {
		return -1
	}
	return beg
}

// func main() {
// 	println(canCompleteCircuit(
// 		[]int{1, 2, 3, 4, 5},
// 		[]int{3, 4, 5, 1, 2}))
// }