Asked in: FLIPKART
Image of the Question
All Testcases Passed ✔
Solution
#include <iostream>
#include <vector>
using namespace std;
// ... rest of solution available after purchaseExplanation
```
To solve this problem, start by carefully understanding the conditions and what is being asked: you have N villages arranged in a circle, each providing a certain number of energy drinks and requiring a certain distance to the next village to travel. The player consumes energy drinks equal to the distance traveled. The objective is to find the earliest village (smallest index) from which the player can start, collect energy drinks, and successfully complete the full circular journey without ever running out of energy.
Step 1: Analyze the Problem Structure
The problem is similar in nature to the classic "gas station" or "circular tour" problem often discussed in algorithmic challenges. The key idea is that you need to ensure that starting from some village, you never have negative leftover energy when moving through each village in order.
The player starts at village S with zero leftover energy. At each village, the player gains some energy drinks and then must spend some to travel to the next village. The leftover energy accumulates, and at no point should it drop below zero.
Step 2: Understand the Feasibility Condition
For the circular trip to be possible, the total amount of energy drinks across all villages must be at least the total distance that must be traveled around the circle. If the sum of all energy drinks is less than the sum of all distances, no solution exists. The problem states a solution always exists, so we can assume total drinks ≥ total distance.
Step 3: Iterate Through the Villages and Track Energy
One straightforward method is to simulate the journey from each possible starting village S, checking if the player can make the full circle without the energy dropping below zero. However, this brute force approach is inefficient, especially for large N (up to 10^5 or more).
Step 4: Leverage the Greedy Approach
A more efficient approach comes from a greedy insight:
- Keep a running total of leftover energy as you move from village to village.
- When the leftover energy becomes negative at some village, it means you cannot start from any village before or at the current one because the energy drops below zero before completing the circle. So you reset your start point to the next village.
- Continue this process until you reach the end of the list.
- The start village you end up with after this process will be the earliest valid starting point.
Why does this work? Because if you fail at village i starting from some earlier village, then no village between the earlier start and i can be a valid start (as you’d run out of energy earlier or at the same point). Thus, you can skip all these and move your start to i + 1.
Step 5: Calculate Running Sums and Identify Start
While iterating, track:
- The total net energy gain or loss (energy drinks minus distance) to confirm overall feasibility.
- The current leftover energy starting from the tentative start village.
If at any point leftover energy drops below zero, reset leftover energy to zero and move the start index to the next village.
Step 6: Final Result
After processing all villages, the chosen start index will be the smallest index (1-based) that allows the player to complete the circular tour.
Step 7: Additional Points and Edge Cases
- Since indexing is 1-based for output, remember to adjust indexes accordingly.
- Handle cases where energy drinks and distances are equal or large integers gracefully (use data types that can hold large sums).
- The circular nature means once you reach the last village, you must check the total feasibility to ensure the journey can wrap around.
Step 8: Summarize the Efficient Approach
- Verify total energy drinks ≥ total distance to ensure a solution exists.
- Initialize start index at 0, leftover energy at 0.
- Traverse the villages in order: at each village add (energy drinks - distance) to leftover energy.
- If leftover energy falls below zero, move start index to the next village and reset leftover energy to zero.
- After completing one full pass, the start index is the minimal valid starting village.
This approach runs in O(N) time, as it involves only a single pass through the array. It efficiently finds the minimal starting village to complete the circular tour without exhaustive checking of all possible starts.
```