Bird
Raised Fist0

Consider the following buggy code snippet for the Gas Station problem: ```python def canCompleteCircuit(gas, cost): if sum(gas) < sum(cost): return -1 start = 0 tank = 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: start = i tank = 0 return start ``` What is the subtle bug causing incorrect results on some inputs?

medium🐞 Bug Identification Q7 of Q15
Greedy Algorithms - Gas Station (Circular)
Consider the following buggy code snippet for the Gas Station problem: ```python def canCompleteCircuit(gas, cost): if sum(gas) < sum(cost): return -1 start = 0 tank = 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: start = i tank = 0 return start ``` What is the subtle bug causing incorrect results on some inputs?
AUsing gas[i] - cost[i] instead of cost[i] - gas[i]
BNot checking total gas vs total cost before loop
CResetting start to i instead of i + 1 when tank < 0
DReturning start without verifying if circuit is possible
Step-by-Step Solution
Solution:
  1. Step 1: Identify reset logic

    When tank < 0, start should be reset to i + 1, not i, because station i cannot be a valid start.
  2. Step 2: Consequence of bug

    Resetting start to i causes the algorithm to retry the same failing station, leading to incorrect results.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Correct reset index is i + 1 to avoid infinite loops [OK]
Quick Trick: Reset start to i+1, not i, when tank < 0 [OK]
Common Mistakes:
MISTAKES
  • Off-by-one error in resetting start index
Trap Explanation:
PITFALL
  • Candidates often reset start incorrectly, causing wrong start index.
Interviewer Note:
CONTEXT
  • Tests attention to off-by-one bugs in greedy resets
Master "Gas Station (Circular)" in Greedy Algorithms

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Greedy Algorithms Quizzes