Suppose there is a circle. There are N petrol pumps on that circle. You will be given two sets of data.
1. The amount of petrol that every petrol pump has.
2. Distance from that petrol pump to the next petrol pump.
Find a starting point where the truck can start to get through the complete circle without exhausting its petrol in between.
Note :  Assume for 1 litre petrol, the truck can go 1 unit of distance.
Example 1:
Input:
N = 4
Petrol = 4 6 7 4
Distance = 6 5 3 5
Output: 1
Explanation: There are 4 petrol pumps with
amount of petrol and distance to next
petrol pump value pairs as {4, 6}, {6, 5},
{7, 3} and {4, 5}. The first point from
where truck can make a circular tour is
2nd petrol pump. Output in this case is 1
(index of 2nd petrol pump).
Your Task:
Your task is to complete the function tour() which takes the required data as inputs and returns an integer denoting a point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). If there exists multiple such starting points, then the function must return the first one out of those. (return -1 otherwise)
Expected Time Complexity: O(N)
Expected Auxiliary Space : O(1)
Constraints:
2 ≤ N ≤ 10000
1 ≤ petrol, distance ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: '''
    lis[][0]:Petrol
    lis[][1]:Distance
'''

class Solution:
    
    #Function to find starting point where the truck can start to get through
    #the complete circle without exhausting its petrol in between.
    def tour(self,lis, n):
        #Code here

Solutions:
class Solution:

	def tour(self, lis, n):
		balance = 0
		kami = 0
		start = 0
		for i in range(n):
			petrol = lis[i][0]
			dis = lis[i][1]
			balance = petrol - dis + balance
			if balance < 0:
				kami = kami + balance
				balance = 0
				start = i + 1
		if balance + kami >= 0:
			return start
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		s = []
		bakaya = 0
		tak = 0
		for i in range(n):
			s = bakaya + lis[i][0] - lis[i][1]
			if s < 0:
				tak = i + 1
				bakaya = 0
				continue
			if s >= 0:
				bakaya = s
		for i in range(0, tak):
			s = bakaya + lis[i][0] - lis[i][1]
			if s < 0:
				return -1
			if s >= 0:
				bakaya = s
		else:
			return tak


class Solution:

	def tour(self, lis, n):
		rPetrol = 0
		petrolSum = 0
		distSum = 0
		start = 0
		for i in range(n):
			petrolSum += lis[i][0]
			distSum += lis[i][1]
			rPetrol += lis[i][0] - lis[i][1]
			if rPetrol < 0:
				start = i + 1
				rPetrol = 0
		if petrolSum < distSum:
			return -1
		else:
			return start


class Solution:

	def tour(self, arr, n):
		start = 0
		kami = 0
		balance = 0
		for i in range(n):
			balance = balance + arr[i][0] - arr[i][1]
			if balance < 0:
				start = i + 1
				kami += balance
				balance = 0
		if kami + balance >= 0:
			return start
		return -1


class Solution:

	def tour(self, arr, n):
		start = 0
		s = 0
		d = 0
		for i in range(n):
			s += arr[i][0] - arr[i][1]
			if s < 0:
				start = i + 1
				d += s
				s = 0
		return start if s + d >= 0 else -1


class Solution:

	def tour(self, lis, n):
		deficit = 0
		balance = 0
		start = 0
		for i in range(n):
			balance += lis[i][0] - lis[i][1]
			if balance < 0:
				deficit += balance
				balance = 0
				start = i + 1
		if balance + deficit < 0:
			return -1
		else:
			return start


class Solution:

	def tour(self, lis, n):
		bal = 0
		start = 0
		deficit = 0
		for i in range(len(lis)):
			(p, d) = lis[i]
			bal += p - d
			if bal < 0:
				deficit += bal
				start = i + 1
				bal = 0
		if bal + deficit >= 0:
			return start
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		start = 0
		curr = 0
		prev = 0
		for i in range(n):
			curr += lis[i][0] - lis[i][1]
			if curr < 0:
				start = i + 1
				prev += curr
				curr = 0
		return start if curr + prev > 0 else -1


class Solution:

	def tour(self, lis, n):
		deficit = 0
		bal = 0
		st = 0
		for i in range(n):
			bal += lis[i][0] - lis[i][1]
			if bal < 0:
				deficit += bal
				st = i + 1
				bal = 0
		if deficit + bal >= 0:
			return st
		return -1


class Solution:

	def tour(self, lis, n):
		start = 0
		pointer = 0
		balance = 0
		totalDistBeforeStartIndex = 0
		totalPetrolNeededForIndex = 0
		totalDist = 0
		totalPetrol = 0
		while pointer < n:
			balance = lis[pointer][0] + balance - lis[pointer][1]
			totalDist += lis[pointer][1]
			totalPetrol += lis[pointer][0]
			pointer += 1
			if balance < 0:
				start = pointer
				balance = 0
				totalDistBeforeStartIndex += totalDist
				totalPetrolNeededForIndex += totalPetrol
				totalDist = 0
				totalPetrol = 0
			if start == n:
				return -1
		if pointer >= n:
			if totalPetrolNeededForIndex + balance - totalDistBeforeStartIndex >= 0:
				return start
			else:
				return -1
		return start


class Solution:

	def tour(self, lis, n):
		i = 0
		while i < n:
			if lis[i][1] > lis[i][0]:
				i += 1
				pass
			else:
				a = 1
				s = 0
				for j in range(n):
					s += lis[(i + j) % n][0] - lis[(i + j) % n][1]
					if s < 0:
						a = 0
						break
				if a == 1:
					return i
				i = i + j
		return -1


class Solution:

	def tour(self, lis, n):
		d = 0
		a = 0
		c = 0
		for i in range(n):
			d += lis[i][0] - lis[i][1]
			if d < 0:
				a += d
				d = 0
				c = i + 1
		return c if d + a >= 0 else -1


class Solution:

	def tour(self, lis, n):
		i = 0
		while i < n:
			if lis[i][1] > lis[i][0]:
				i += 1
				pass
			else:
				flag = 1
				summ = 0
				for j in range(n):
					summ += lis[(i + j) % n][0] - lis[(i + j) % n][1]
					if summ < 0:
						flag = 0
						break
				if flag == 1:
					return i
				i = i + j
		return -1


class Solution:

	def tour(self, l, n):
		i = 0
		while i < n:
			if l[i][1] > l[i][0]:
				i += 1
				pass
			else:
				t = 1
				s = 0
				for j in range(n):
					s += l[(i + j) % n][0] - l[(i + j) % n][1]
					if s < 0:
						t = 0
						break
				if t == 1:
					return i
				i = i + j
		return -1


class Solution:

	def tour(self, lis, n):
		start = 0
		curr_petrol = 0
		total_petrol = 0
		for i in range(n):
			curr_petrol += lis[i][0] - lis[i][1]
			total_petrol += lis[i][0] - lis[i][1]
			if curr_petrol < 0:
				start = i + 1
				curr_petrol = 0
		return start if total_petrol >= 0 else -1


class Solution:

	def tour(self, lis, n):
		ps = 0
		ds = 0
		rf = 0
		start = 0
		for i in range(n):
			ps += lis[i][0]
			ds += lis[i][1]
			rf += lis[i][0] - lis[i][1]
			if rf < 0:
				start = i + 1
				rf = 0
		if ps < ds:
			return -1
		return start


class Solution:

	def tour(self, lis, n):
		if sum((i[0] for i in lis)) < sum((i[1] for i in lis)):
			return -1
		total = 0
		start = 0
		for i in range(n):
			total += lis[i][0] - lis[i][1]
			if total < 0:
				total = 0
				start = i + 1
		return start


class Solution:

	def tour(self, lis, n):
		start = 0
		deficit = 0
		total = 0
		for i in range(n):
			(petrol, distance) = lis[i]
			deficit += petrol - distance
			total += petrol - distance
			if deficit < 0:
				start = i + 1
				deficit = 0
		if total < 0:
			return -1
		return start


class Solution:

	def tour(self, lis, n):
		fuel = 0
		d = 0
		s = 0
		for i in range(n):
			fuel += lis[i][0] - lis[i][1]
			if fuel < 0:
				d += fuel
				fuel = 0
				s = i + 1
		return s if fuel + d >= 0 else -1


class Solution:

	def tour(self, lis, n):
		start = 0
		end = 1
		curr_petrol = lis[start][0] - lis[start][1]
		while end != start or curr_petrol < 0:
			while curr_petrol < 0 and start != end:
				curr_petrol -= lis[start][0] - lis[start][1]
				start = (start + 1) % n
				if start == 0:
					return -1
			curr_petrol += lis[end][0] - lis[end][1]
			end = (end + 1) % n
		return start


class Solution:

	def tour(self, lis, n):
		balance = 0
		front = 0
		flag = 0
		i = 0
		while i < n:
			balance = balance + lis[i][0]
			balance = balance - lis[i][1]
			if balance >= 0:
				if flag == 0:
					front = i
					flag = 1
			else:
				front = -1
				balance = 0
				flag = 0
			i = i + 1
		i = 0
		while i < front:
			balance = balance + lis[i][0]
			balance = balance - lis[i][1]
			if balance >= 0:
				if flag == 0:
					front = i
					flag = 1
			else:
				front = -1
				balance = 0
				flag = 0
			i = i + 1
		return front


class Solution:

	def tour(self, lis, n):
		i = 0
		while i < n:
			if lis[i][1] > lis[i][0]:
				i += 1
				pass
			else:
				set_flg = 1
				res = 0
				for j in range(n):
					res += lis[(i + j) % n][0] - lis[(i + j) % n][1]
					if res < 0:
						set_flg = 0
						break
				if set_flg == 1:
					return i
				i = i + j
		return -1


class Solution:

	def tour(self, arr, n):
		start = 0
		deficit = 0
		total_deficit = 0
		for i in range(n):
			(petrol, distance) = arr[i]
			deficit += petrol - distance
			total_deficit += petrol - distance
			if deficit < 0:
				start = i + 1
				deficit = 0
		if total_deficit < 0:
			return -1
		return start


class Solution:

	def tour(self, lis, n):
		tank = 0
		start = -1
		tankRequired = 0
		total = 0
		for i in range(n):
			(petrol, distance) = lis[i]
			total += petrol - distance
			if start < 0:
				start = i
			tank = tank - distance + petrol
			if tank < 0:
				tankRequired = abs(tank)
				start = -1
				tank = 0
		return start if total >= 0 else -1


class Solution:

	def tour(self, lis, n):
		petrol = 0
		index = -1
		sum1 = 0
		sum2 = 0
		for i in range(n):
			sum1 += lis[i][0]
			sum2 += lis[i][1]
			petrol += lis[i][0] - lis[i][1]
			if petrol < 0:
				petrol = 0
				index = -1
			elif index < 0:
				index = i
		if sum1 < sum2:
			return -1
		return index


class Solution:

	def tour(self, lis, n):
		data = [a[0] - a[1] for a in lis]
		if sum(data) == 0:
			return -1
		(st, cap, deff) = (0, 0, 0)
		for j in range(n):
			cap += data[j]
			if cap < 0:
				st = j + 1
				deff += cap
				cap = 0
		if st >= n:
			return -1
		elif cap + deff >= 0:
			return st
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		data = [a[0] - a[1] for a in lis]
		if sum(data) < 0:
			return -1
		start = 0
		deficit = 0
		capacity = 0
		for i in range(n):
			capacity += data[i]
			if capacity < 0:
				start = i + 1
				deficit += capacity
				capacity = 0
		if start == n:
			return -1
		if capacity + deficit >= 0:
			return start
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		extrafuel = 0
		requiredfuel = 0
		start = 0
		for i in range(n):
			extrafuel += lis[i][0] - lis[i][1]
			if extrafuel < 0:
				start = i + 1
				requiredfuel += extrafuel
				extrafuel = 0
		if extrafuel + requiredfuel >= 0:
			return start
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		start = 0
		extra_fuel = 0
		required_fuel = 0
		for i in range(n):
			extra_fuel += lis[i][0] - lis[i][1]
			if extra_fuel < 0:
				required_fuel += extra_fuel
				extra_fuel = 0
				start = i + 1
		if extra_fuel + required_fuel >= 0:
			return start
		return -1


class Solution:

	def tour(self, lis, n):
		cal = 0
		d = 0
		start = 0
		for i in range(0, n):
			cal += lis[i][0] - lis[i][1]
			if cal < 0:
				start = i + 1
				d += cal
				cal = 0
		return start if cal + d > 0 else -1


class Solution:

	def tour(self, lis, n):
		a = 0
		b = 0
		for i in range(n):
			a = a + lis[i][0]
			b = b + lis[i][1]
		if b > a:
			return -1
		res = 0
		c = 0
		for i in range(n):
			res = res + (lis[i][0] - lis[i][1])
			if res < 0:
				res = 0
				c = i + 1
		return c


class Solution:

	def tour(self, lis, n):
		sum_petrol = 0
		sum_distance = 0
		for i in range(n):
			sum_petrol += lis[i][0]
			sum_distance += lis[i][1]
		if sum_petrol < sum_distance:
			return -1
		else:
			fuel = 0
			start = 0
			for i in range(n):
				fuel += lis[i][0] - lis[i][1]
				if fuel < 0:
					fuel = 0
					start = i + 1
			return start


class Solution:

	def tour(self, lis, n):
		start = 0
		curr_pet = 0
		prev_pet = 0
		for i in range(n):
			curr_pet += lis[i][0] - lis[i][1]
			if curr_pet < 0:
				start = i + 1
				prev_pet += curr_pet
				curr_pet = 0
		if curr_pet + prev_pet >= 0:
			return start
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		lst = []
		for i in range(n):
			diff = lis[i][0] - lis[i][1]
			lst.append(diff)
		dist = 0
		deficit = 0
		index = 0
		for i in range(n):
			dist += lst[i]
			if dist < 0:
				index = i + 1
				deficit += dist
				dist = 0
		if dist + deficit >= 0:
			return index
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		oh = 0
		buf = 0
		sp = 0
		for i in range(0, n):
			buf += lis[i][0] - lis[i][1]
			if buf < 0:
				sp = i + 1
				oh += abs(buf)
				buf = 0
		if oh <= buf:
			return sp
		return -1


class Solution:

	def tour(self, lis, n):
		petrol = sum([i for (i, j) in lis])
		distance = sum([j for (i, j) in lis])
		if distance > petrol:
			return -1
		temp = 0
		start = 0
		for i in range(n):
			temp += lis[i][0] - lis[i][1]
			if temp < 0:
				temp = 0
				start = i + 1
		return start


class Solution:

	def tour(self, lis, n):
		n = len(lis)
		total_gas = 0
		for i in range(n):
			total_gas += lis[i][0]
		total_cost = 0
		for i in range(n):
			total_cost += lis[i][1]
		if total_gas < total_cost:
			return -1
		total = 0
		res = 0
		for i in range(n):
			gas = lis[i][0]
			cost = lis[i][1]
			total += gas - cost
			if total < 0:
				total = 0
				res = i + 1
		return res


class Solution:

	def tour(self, lis, n):
		total_petrol = 0
		total_distance = 0
		start = 0
		end = 0
		while True:
			if start == n:
				return -1
			total_petrol += lis[end][0]
			total_distance += lis[end][1]
			while total_distance > total_petrol and start != n:
				total_petrol -= lis[start][0]
				total_distance -= lis[start][1]
				start = start + 1
			end = (end + 1) % n
			if end == start and total_distance != 0:
				return start


class Solution:

	def tour(self, lis, n):
		new_start = 0
		stored = 0
		prev_stored = 0
		curr_stored = 0
		for i in range(0, n):
			curr_stored += lis[i][0] - lis[i][1]
			if curr_stored < 0:
				new_start = i + 1
				prev_stored += curr_stored
				curr_stored = 0
		if curr_stored + prev_stored >= 0:
			return new_start
		else:
			return -1


class Solution:

	def tour(self, lis, n):
		diff = [0 for i in range(n)]
		current_petrol = 0
		startingPoint = 0
		deficit = 0
		for i in range(n):
			diff[i] = lis[i][0] - lis[i][1]
			current_petrol += diff[i]
			if current_petrol < 0:
				startingPoint = i + 1
				deficit += current_petrol
				current_petrol = 0
		return startingPoint if deficit + current_petrol >= 0 else -1


class Solution:

	def tour(self, lis, n):
		tp = 0
		td = 0
		for (a, b) in lis:
			tp += a
			td += b
		if td > tp:
			return -1
		i = 0
		cp = 0
		ans = 0
		while i < len(lis):
			if cp + lis[i][0] >= lis[i][1]:
				cp -= lis[i][1]
				cp += lis[i][0]
				i += 1
			else:
				i += 1
				ans = i
				cp = 0
		return ans


class Solution:

	def tour(self, lis, n):
		lis = lis + lis
		i = 0
		start = i
		curr = 0
		while i < 2 * n:
			if i == start + n:
				return start
			curr = curr + lis[i][0] - lis[i][1]
			if curr < 0:
				start = i + 1
				curr = 0
			i += 1
		return -1


class Solution:

	def tour(self, lis, n):
		index = None
		cur = 0
		for i in range(n):
			cur += lis[i][0] - lis[i][1]
			if cur < 0:
				cur = 0
				index = None
			elif index == None:
				index = i
		if index == None:
			return -1
		s = 0
		for i in range(index):
			s += lis[i][0] - lis[i][1]
		if s + cur < 0:
			return -1
		return index


class Solution:

	def tour(self, lis, n):
		start = 0
		petrol = 0
		deficiet = 0
		for i in range(n):
			petrol = petrol + lis[i][0] - lis[i][1]
			if petrol < 0:
				start = i + 1
				deficiet = deficiet + petrol
				petrol = 0
		if deficiet + petrol >= 0:
			return start
		else:
			return -1