Gas Tank Problem Statement

You have a car with a gas tank of infinite capacity. There are 'N' gas stations located along a circular route, numbered from 0 to N-1. You begin your journey with an empty tank from one of these stations. The objective is to complete one full clockwise traversal around the circular route. That means if you start from station 'i', you will pass through i+1, i+2, ..., N-1, 0, 1, ..., i-1, and finally return back to 'i'.

You are provided with two integer arrays, gas and cost. The element gas[i] indicates the amount of gas available at station 'i', and cost[i] denotes the amount of gas required to travel from station 'i' to the next station (i.e., station i+1, or 0 if station is N-1).

Your task is to find the starting gas station's index that allows you to complete the circle once. If there are multiple potential starting points, select the smallest index. If completing the circle isn't possible from any starting point, return -1.

Example:

Input:
T = 1
N = 5
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
Output:
3
Explanation:

Starting at station 3, the car can complete a full circle as it accumulates enough gas to travel each segment.

Constraints:

  • 1 <= T <= 50
  • 1 <= N <= 104
  • 0 <= GAS[i] <= 105
  • 0 <= COST[i] <= 105
AnswerBot
4d

Find the starting gas station index to complete a circular route with gas and cost arrays.

  • Iterate through gas stations, keeping track of gas remaining after each station

  • If gas remaining is negative, r...read more

Help your peers!
Add answer anonymously...
Mahindra Logistics Software Developer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter